Dynamic Programming Recursion and a sprinkle of Memoization

Question

I have this massive array of ints from 0-4 in this triangle. I am trying to learn dynamic programming with Ruby and would like some assistance in calculating the number of paths in the triangle that meet three criterion:

1. You must start at one of the zero points in the row with 70 elements.
2. Your path can be directly above you one row (if there is a number directly above) or one row up heading diagonal to the left. One of these options is always available
3. The sum of the path you take to get to the zero on the first row must add up to 140.

Example, start at the second zero in the bottom row. You can move directly up to the one or diagonal left to the 4. In either case, the number you arrive at must be added to the running count of all the numbers you have visited. From the 1 you can travel to a 2 (running sum = 3) directly above or to the 0 (running sum = 1) diagonal to the left.

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

But I like homework :)

I find it easier to reason about the 'paths' problem when starting from the top, and following the rules the other way around.

This means:

• a partial path can be the top zero, or an extended partial path
• the extensions of a partial path Pr,c are, unless r is the last row, in which they're complete, the union of
  • the extensions of Pr,c + P(r+1),c
  • the extensions of Pr,c + P(r+1),c+1

The 'sum' rule just selects certain of all complete paths.