1

この三角形には、0 から 4 までの整数の膨大な配列があります。私は Ruby で動的プログラミングを学ぼうとしていますが、次の 3 つの基準を満たす三角形内のパスの数を計算する際に助けが必要です。

  1. 70 要素の行のゼロ点の 1 つから開始する必要があります。
  2. あなたのパスは、あなたの 1 行真上 (真上に数字がある場合) または 1 行上、左斜め上にある可能性があります。これらのオプションのいずれかが常に利用可能です
  3. 最初の行のゼロに到達するまでの経路の合計は、140 になる必要があります。

たとえば、一番下の行の 2 番目のゼロから開始します。1 まで直接移動することも、左斜め 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
4

1 に答える 1

1

でも宿題は好きです:)

「パス」の問題については、上から始めて、その逆のルールに従う方が簡単だと思います。

これの意味は：

  • 部分パスは、先頭のゼロまたは拡張された部分パスにすることができます
  • 部分パス Pr,c の拡張は、r が完全な最後の行でない限り、次の和集合です。
    • Pr,c + P(r+1),c の拡張
    • Pr,c + P(r+1),c+1 の拡張

「合計」ルールは、すべての完全なパスから特定のものを選択するだけです。

于 2009-03-25T21:44:18.443 に答える