3

ですから、基本的に私は信じられないほど馬鹿げていると感じています。この演習のおかげで、コーディングに4〜5時間費やしましたが、これまでのところ成功していません。

これは、最長パスアプローチを使用したツリートラバーサルで解決する方が簡単であることに気付きましたが、よくわかりません（これを確認してください） 。簡単な問題の1つです。では、これを解決するためのガイダンス、基本的な手順、またはアルゴリズムのアプローチについて教えてください。あらゆる種類の助けが確かにありがたいです。

PS。私は通常、これまでに行ったことに関するコードを投稿しますが、これまでのところすべてが間違っているため、少なくともアイデアの観点からはゼロから始めることを好みます。

ありがとう。

リクエストごとに、演習を解決するために受け入れられた回答に従って入力したコードは次のとおりです。

def get_max_sum(matrix)
  (1...matrix.length).each do |index|  
    flag = 0  
    matrix[index].each_with_index do |e, i|    
      add = (matrix[index-1][flag] > matrix[index-1][flag+1]) ? matrix[index-1][flag] : matrix[index-1][flag+1]
      e += add
      matrix[index][i] = e
      flag = flag + 1
    end    
  end
  matrix[-1][0]
end

ここで、matrix paramは配列の配列であり、各配列は三角形の行を表します。

4

3 に答える 3

6

この問題は、下から始めて上に向かっていくと簡単です。三角形を考えてみましょう

   1
  1 2
 4 1 2
2 3 1 1

最後から2番目の行を見てください。三角形を通るパスで4に到達した場合は、右に3に移動し、合計7（およびその上のパスにあるもの）を与えます。1に達した場合は、左に3に移動し、合計4（およびその上のパスにあるもの）を与えます。2にいる場合は、どちらの方向にも合計3（およびその上のパスにあるもの）で移動できます。したがって、最後から2番目の行を合計に置き換えることにより、三角形は

  1
 1 2
7 4 3

元の三角形と同じ最大合計パスを持ちます。次に、縮小された三角形に対して同じプロセスを再帰的に実行します。最後から2番目の行の1から7に左に移動すると、合計が8になり、2から左に移動して4に移動すると、合計が6になります。縮小された三角形は次のようになります。

 1
8 6

最後に、最後から2番目の行の1から左に8に移動し、合計9を求めます。これが問題の答えです。

トップダウンで作業する方法もあります。各ステップで、三角形の各数値を、その数値につながるパスの最大合計に置き換えます。上から始めて、三角形が始まります

1

次に、2番目の行がその合計に置き換えられます

 1
2 3

次に3行目

  1
 2 3
6 4 5

そして最後に4列目

   1
  2 3
 6 4 5
8 9 6 6

答えは、一番下の行の最大の合計である9です。トップダウンのアプローチはボトムアップのアプローチよりも管理が難しいといつも思っていますが、2つのアルゴリズムは互いに二重であるため、どちらを選択するかを選択します。実装する。トップダウンアプローチには、データを読み取っているときに次の行を累積できるという利点があります。ボトムアップアプローチでは、合計を計算する前に、入力全体を読み取って保存する必要があります。

コードを書くのはあなたに任せます。その場合、一度に格納する必要があるのは、前の行と次の行の2つの行だけであることを忘れないでください。前の行と次の行は、トップダウンで作業しているかボトムアップで作業しているかによって異なります。前の行は入力したばかりの行で、次の行は現在作業している行です。つまり、トップダウンで作業している場合、次の行の合計は前の行より1つ多く、ボトムアップで作業している場合、次の行の合計は前の行より1つ少なくなります。他の人があなたの努力から学ぶことができるように、あなたがそれを機能させるときにあなたのコードを投稿してください。

ちなみに、この問題はもともとプロジェクトオイラーに起因しています。コードシェフは、明らかに帰属なしに、彼らからそれを盗みました。これは、実際にはあまり良いことではありません。

于 2012-05-22T04:04:35.720 に答える
1

注：元の投稿の問題の説明は、直角三角形を想定しています。

on each path the next number is located on the row below,
more precisely either directly below or below and one place to the right.

また、これを確認するために彼らが提供する例を見てください。

答え：

  • 1]2次元配列を使用して三角形を格納します

  • ルールに基づいて三角形を再計算します

  • 三角形の最後の行、つまり底辺を歩いて、最大値を見つけます。

コード：

import java.util.Arrays;

public class NumberTriangle {

    //MAIN IS FOR TESTING ONLY
public static void main(String[] ars) {
    int[][] input = { { 1 }, { 4, 8 }, { 9, 8, 7 }, { 1, 3, 6, 9 },
            { 7, 5, 2, 7, 3 } };

    int max = compute(input);// answer: max length
    // not necessary; but shows new triangle
    for (int[] A : input)
        System.out.println(Arrays.toString(A));

    // print the answer
    System.out.println("Largest number: " + max);
}

    //THIS IS THE SOLUTION
public static int compute(int[][] input) {
    //compute new triangle
    for (int y = 1; y < input.length; y++)
        for (int x = 0; x < input[y].length; x++) {
            int first = x - 1 > 0 ? x - 1 : 0;
            int last = x < input[y - 1].length ? x
                    : input[y - 1].length - 1;
            int max = Math.max(input[y - 1][last], input[y - 1][first]);
            input[y][x] += max;
        }
    //extract max value;
    int max = -1;
    int lastRow = input[input.length - 1].length;
    for (int x = 0, y = input.length - 1; x < lastRow; x++)
        if (max < input[y][x])
            max = input[y][x];
    return max;
}// compute
}

テストケースの回答：

[1]
[5, 9]
[14, 17, 16]
[15, 20, 23, 25]
[22, 25, 25, 32, 28]

Largest number: 32
于 2012-05-22T03:08:02.800 に答える
0

すべてのパスがN-1エッジの長さになるため、最長パスファインディングアプローチは私には間違ったアプローチのように感じます。入力が二分木のように見せかけて、ツリー内の最大の要素を見つけることからアプローチを開始すると思います。下の2行の最大の合計を見つけ、最後から2番目の行に結果をメモしてから、別の行に移動します。行。（それが何らかの意味をなすといいのですが...）

于 2012-05-22T01:29:34.457 に答える