を通過する経路の最大合計は、基本的に私は、これと似たものだという問題があります。各植物（各要素）には多数のイチゴがあります。配列の左上隅から開始し、右または下に移動することができます。私は、庭を通る経路を計算し、次にどれが最もイチゴをもたらすかを再帰的に計算する方法を設計する必要があります。Javaの2次元配列
私は本当に本当に単純な再帰問題について理解していると思いますが、この問題は私の頭上にあります。私は再帰的な方法を作成するところまで、どこからどこに行かなければならないのか、どこに行くのかは分かりません。
この問題の背後にある概念を理解するのに役立つコードや助けがあれば、大歓迎です。ありがとう。
dasblinkenlightと同様に、これを行う最も効率的な方法は、メモや動的プログラミング技術を使用することです。私は動的プログラミングを好む傾向がありますが、ここでは純粋な再帰を使用します。
答えは基本的な質問の答えを中心にしています。「自分のフィールドの行rと列cの正方形にある場合、左上からここまでのパスをどのように評価してイチゴは最大化されていますか？ "
実現する鍵は、行rと列cのプロットに入る方法が2つしかないということです。行r-1と列cのプロットを使用して上から取得できます。行rと列c-1のプロットを使って、側から
int[][] field;
int max(int r, int c) {
//Base case
if (r == 0 && c == 0) {
return field[r][c];
}
//Assuming a positive number of strawberries in each plot, otherwise this needs
//to be negative infinity
int maxTop = -1, maxLeft = -1;
//We can't come from the top if we're in the top row
if (r != 0) {
maxTop = field[r-1][c];
}
//Similarly, we can't come from the left if we're in the left column
if (c != 0) {
maxLeft = field[r][c-1];
}
//Take whichever gives you more and return..
return Math.max(maxTop, maxLeft) + field[r][c];
}
コールMAX（R-1、C-1）へ：あなただけを意味している...あなたは基本例を知っていることを確認する必要があり、その後、基本的に、私の純粋に再帰的なバージョンは次のようなものになるだろうあなたの答えを得る。ここには多くの非効率性があることに注意してください。動的プログラミング（以下で説明します）またはメモ（既に定義されています）を使用すると、よりうまくいくでしょう。しかし、覚えておくべきことは、DP法とメモ法は、ここで使用されている再帰的原理に由来する単純に効率的な方法であるということです。
DP：あなたは実際のパスを再作成したい場合は、両方のケースで
int maxValue(int[][] field) {
int r = field.length;
int c = field[0].length;
int[][] maxValues = new int[r][c];
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (i == 0 && j == 0) {
maxValues[i][j] = field[i][j];
} else if (i == 0) {
maxValues[i][j] = maxValues[i][j-1] + field[i][j];
} else if (j == 0) {
maxValues[i][j] = maxValues[i-1][j] + field[i][j];
} else {
maxValues[i][j] = Math.max(maxValues[i][j-1], maxValues[i-1][j]) + field[i][j];
}
}
}
return maxValues[r-1][c-1];
}
、単に「私は左の上かから来たの」に対応するブールの2Dテーブルを維持？最もイチゴのパスが上記のものである場合はtrueを、それ以外の場合はfalseを入れます。これにより、計算後にパッチを戻すことができます。
これはまだ原則的に再帰的であることに注意してください。各ステップで、以前の結果を振り返ります。私たちは以前の結果をキャッシュしているので、作業を無駄にすることはありません。私たちは、問題を常に解決できるように、インテリジェントな順序でサブプログラムを攻撃しています。動的プログラミングの詳細については、Wikipediaを参照してください。
おそらく 'return maxValues [r-1] [c-1]; 'を意味します。 – Quixotic
おっと、ありがとう！ – DivineWolfwood
こんにちはDivineWolfwood、あなたの例は非常に込み入っています。しかし、私は左と右の両方を見たいのですか？ – Doro
memoizationを使用してください。 Javaのような疑似コード（memo、R、およびCは、maxメソッドで使用できるインスタンス変数とみなされます）。
int R = 10, C = 20;
int memo[][] = new int[R][C];
for (int r=0 ; r != R ; r++)
for (int c = 0 ; c != C ; c++)
memo[r][c] = -1;
int res = max(0, 0, field);
int max(int r, int c, int[][] field) {
if (memo[r][c] != -1) return memo[r][c];
int down = 0; right = 0;
if (r != R) down = max(r+1, c, field);
if (c != C) right = max(r, c+1, field);
return memo[r][c] = (field[r][c] + Math.max(down, right));
}
お元気ですか、でも** [ちょっと複雑な仕事]（http://stackoverflow.com/q/42706957/2650174）**でお手伝いできますか？ –
これは、O（m * n）からO（n）だけにスペースを節約できるDP集計方法で解決できます。 DP Memorizationでは、中間値を格納するにはm * n行列が必要です。以下は私のPythonコードです。それが役立つことを願っています。
def max_path(field):
dp = [sum(field[0][:i]) for i in range(1, len(field[0]) + 1)]
for i in range(1, len(field)):
for j in range(len(dp)):
dp[j] = min(dp[j], dp[j - 1] if j > 0 else float('inf')) + field[i][j]
return dp[-1]
再帰的でなければなりませんか？反復はここではより簡単になります。 –
はい、再帰的である必要があります。 – user1547050
さて、dasblinkenlightの答えはうまくいきますが、右に行くか右にするかを追跡するだけで大きな数字が得られます。 –