動的プログラミング再帰とメモの振り分け

Question

私は、この三角形の中に0-4のintの大規模な配列を持っています。あなたは70個の要素と行内のゼロ点の一つで開始する必要があります

1. ：私は、Rubyとの動的なプログラミングを学び、3つの基準を満たす三角形のパスの数を計算するには、いくつかの支援をしたいと思いますしようとしています。
2. あなたのパスは、1行（真上の数字がある場合）または左上の1行の上に置くことができます。これらのオプションの一つは、常に
3. あなたは140

例にならなければならない最初の行にゼロに到達するために要するパスの合計で利用可能である、下の行の2番目のゼロから始まります。いずれかの場合は、あなたが訪れたすべての番号の実行カウントに、あなたが到着した番号を加えなければなりません。 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

しかし、私のような宿題:)

私は上から順に、ルールに他の方法で回避し、次の時にそれが簡単に「パス」問題について推論することを見つけます。

これが意味：

• をrがする、最後の行でない限り、部分パスは、部分パスのPrの拡張上部ゼロ、または拡張部分パス
• することができ、cは、あります彼らは、完全なPR、C + P（R + 1）の
  • 拡張、PR、C + P（R + 1）の
  • Cの拡張機能の組合、C + 1
  です

'sum'ルールは、すべての完全パスを選択するだけです。