Динамическое программирование, рекурсия и брызги мемоизации

Question

У меня есть этот массив массивов от 0-4 в этом треугольнике. Я пытаюсь изучить динамическое программирование на Ruby и хотел бы получить некоторую помощь в расчете числа путей в треугольнике, которые соответствуют трем критериям:

1. Вы должны начать с одной из нулевых точек в строке с 70 элементами.
2. Ваш путь может быть непосредственно над вами на один ряд (если число находится прямо над ним) или на один ряд вверх по диагонали влево. Один из этих вариантов всегда доступен
3. Сумма пути, по которому вы идете к нулю в первой строке, должна составлять до 140.

Пример, начинайте со второго нуля в нижнем ряду. Вы можете перейти прямо вверх или на одну диагональ влево до 4. В любом случае полученный вами номер должен быть добавлен к текущему счету всех номеров, которые вы посетили. От 1 вы можете перейти к 2 (текущая сумма = 3) прямо выше или к 0 (текущая сумма = 1) диагонали влево.

0  
41  
302  
2413  
13024  
024130  
4130241  
30241302  
241302413  
1302413024  
02413024130  
413024130241  
3024130241302  
24130241302413  
130241302413024  
0241302413024130  
41302413024130241  
302413024130241302  
2413024130241302413  
13024130241302413024  
024130241302413024130  
4130241302413024130241  
30241302413024130241302  
241302413024130241302413  
1302413024130241302413024  
02413024130241302413024130  
413024130241302413024130241  
3024130241302413024130241302  
24130241302413024130241302413  
130241302413024130241302413024  
0241302413024130241302413024130  
41302413024130241302413024130241  
302413024130241302413024130241302  
2413024130241302413024130241302413  
13024130241302413024130241302413024  
024130241302413024130241302413024130  
4130241302413024130241302413024130241  
30241302413024130241302413024130241302  
241302413024130241302413024130241302413  
1302413024130241302413024130241302413024  
02413024130241302413024130241302413024130  
413024130241302413024130241302413024130241  
3024130241302413024130241302413024130241302  
24130241302413024130241302413024130241302413  
130241302413024130241302413024130241302413024  
0241302413024130241302413024130241302413024130  
41302413024130241302413024130241302413024130241  
302413024130241302413024130241302413024130241302  
2413024130241302413024130241302413024130241302413  
13024130241302413024130241302413024130241302413024  
024130241302413024130241302413024130241302413024130  
4130241302413024130241302413024130241302413024130241  
30241302413024130241302413024130241302413024130241302  
241302413024130241302413024130241302413024130241302413  
1302413024130241302413024130241302413024130241302413024  
02413024130241302413024130241302413024130241302413024130  
413024130241302413024130241302413024130241302413024130241  
3024130241302413024130241302413024130241302413024130241302  
24130241302413024130241302413024130241302413024130241302413  
130241302413024130241302413024130241302413024130241302413024  
0241302413024130241302413024130241302413024130241302413024130  
41302413024130241302413024130241302413024130241302413024130241  
302413024130241302413024130241302413024130241302413024130241302  
2413024130241302413024130241302413024130241302413024130241302413  
13024130241302413024130241302413024130241302413024130241302413024  
024130241302413024130241302413024130241302413024130241302413024130  
4130241302413024130241302413024130241302413024130241302413024130241  
30241302413024130241302413024130241302413024130241302413024130241302  
241302413024130241302413024130241302413024130241302413024130241302413  
1302413024130241302413024130241302413024130241302413024130241302413024  
02413024130241302413024130241302413024130241302413024130241302413024130  

Answer 1

Но я люблю домашнее задание:)

Мне легче рассуждать о проблеме «путей», когда начинаешь сверху, а наоборот, следую правилам.

Это означает:

• частичный путь может быть верхним нулем или расширенным частичным путем
• расширения частичного пути Pr, c, если r не последняя строка, в которой они завершены, объединение
  • расширения Pr, c + P (r + 1), c
  • расширения Pr, c + P (r + 1), c + 1

Правило «сумма» просто выбирает некоторые из полных путей.