[白俊2579-階段を登る-Java]

6074 ワード
テキストリンク

もんだいぶんせき


DP

時間の複雑さ


DPはO(N)問題を解決できる

インプリメンテーション


1.テーブルの定義
int[][] table = new int[300+1][2+1];
// table[i][1] = i번째 계단을 연속해서 1개의 계단을 밟고 올라온 경우, 단 현재 계단을 포함해서
// table[i][2] = i번쩨 계단을 연속해서 2개의 게단을 밟고 올라온 경우, 단 현재 계단을 포함해서
2.点火式を得る
table[i][1] = Math.max(table[i-2][2], table[i-2][1]) + stair[i]; //...1
table[i][2] = table[i-1][1] + stair[i]; //...2

  • つまり、現在の階段を含めて、連続して1つの階段を歩きました.つまり、2つの階段から下りた階段が相応の階段に来ています.

  • これは、現在の階段を含めて、2つの階段を連続して歩いたことを意味します.つまり、1段以下の階段から相応の階段に来ています.現在の階段を含めて2つの階段を連続して歩いたため、table[i-1][2]は考慮対象から除外された.table[i-1][2]は既にi-1段まで連続して歩いた時の点数なので、table[i-1][2]を考えると3段連続して歩いた場合も考えられます.
    • 3.初期値の設定
    table[1][1] = stair[1];
table[1][2] = -1; // 논리적으로 말이 안되는 상황.

table[2][1] = stair[2];
table[2][2] = stair[1] + stair[2];

    さまよう部分


    解答が見られなかったら解けなかったような…うろうろしているというより、全然解けなかった.

    その他の方法


    以上の講義は2つの解題方法を説明した.
    バッキン監督

    取得する

  • 実際、この問題を通して、DPは単純に解題方法を身につけているわけではなく、知識を増やすことはできないことが分かりました.
  • 最終的には、テーブルを定義し、点火式を確立する練習をたくさんしなければなりません.

    • 完全コード[マイコード-Java]


    に感銘を与える


    DPには近道がないようです.本当に多くの問題を解決する方法しかないようです.

    リファレンス


    実戦アルゴリズムを教えてあげる
    HTML 5キャンバスのサイズ変更とスプライトのスケーリング
    macのつらい日本語ホームディレクトリを英語にする