タスク定義:
自然数の行列があります。タスクは、マトリックスの左上隅からマトリックスの右下隅までのパスを見つけ、最大スコアをダイヤルすることです。ナビゲーションのルール: [i][j] にいる場合は、次のように移動できます: a) [i][j-1]、[i][j+1]、[i+1][j] セル、およびゼロ点 b) を [i+1][j+1] にダイヤルし、行列 [i][j] ポイントをダイヤルします。
ちょっとした例:
score 50あなたが持っていると仮定しますmatrix
0 3 5 3 2
4 7 2 5 2
4 3 5 2 5
[1][1] セル (行列 [1][1] = 7) にいるとします。次の場所に移動できます。
a) [1][0] cell with 50 score
b) [1][2] cell with 50 score
c) [2][1] cell with 50 score
d) [2][2] cell with 57 score
なんて問題：
私はこのタスクを非常に遅い方法で解決します...
再帰の助けを借りて実装しようとしています。最大スコアを見つけたいだけなら簡単です。何かのようなもの
public int loop(int i, int j) {
int left = loop(i, j-1);
int top = loop(i-1, j);
int diagonal = loop(i-1,j-1) + matrix[i-1][j-1];
return maximum(left, top, diagonal);
}
でも、スコアが最大になるパスを見つけたい！そして、それは非常に時間/メモリを消費します。
時間/メモリを消費する理由:
問題が 1 つあります。パス コレクションを保存し、それをパラメーターとしてループ メソッドに渡す必要があります。しかし、ループ メソッドは反復ごとにフォークし、パス コレクションを 3 回反復してコピーする必要があります。そうしないと、各ループ フォークが共通のパス コレクションを変更し、最終的にすべての可能なパスが含まれます。if between left, top&diagonal最大のことは、 andleftにリンクされたパスを含めてはならないということです。topdiagonal
質問：
正しい方法で解決するには？
編集：
実際には、完全なパスを見つける必要はありません。スコアをダイヤルするポイント (斜めに移動するポイント) を見つけるだけで済みます。