LeetCode Day動的プログラミング Part1

509. フィボナッチ数

一般に F(n) と示されるフィボナッチ数は、フィボナッチ数列と呼ばれる数列を形成します。各数は、0 と 1 から始まる先行する 2 つの数の合計になります。つまり、

F(0) = 0、F(1) = 1
F(n) = F(n - 1) + F(n - 2)、n > の場合1.
n が与えられた場合、F(n) を計算します。

例 1:

入力: n = 2
出力: 1
説明: F(2) = F(1) + F(0) = 1 + 0 = 1.
例 2:

入力: n = 3
出力: 2
説明: F(3) = F(2) + F(1) = 1 + 1 = 2.
例 3:

入力: n = 4
出力: 3
説明: F(4) = F(3) + F(2) = 2 + 1 = 3.

制約:

0 オリジナルページ

再帰メソッド

    public int fib(int n) {
        if(n==0){
            return 0;
        }     
        else if(n==1){
            return 1;
        }   
        else{
            return fib(n-1) + fib(n-2);
        }
    }

再帰法は、深く掘り下げて最終的な答えを得るためにバックトラッキングを行う DFS に似ています。
時間: O(2^n)
スペース: O(1)

    private int[] dp = new int[31];
    public int fib(int n) {
        if(n<2){
            dp[n] = n;
            return n;
        }  

        if(n>=2 && dp[n]!=0){
            return dp[n];
        }

        dp[n] = fib(n-1) + fib(n-2);
        return dp[n];
    }

同じ要素の再帰を避けるために、グローバル配列を使用して結果を保存できます。例えば下の図は、f(17) と f(18) が 2 つの異なる再帰ルートであり、通常の再帰方法を使用する場合、それらを複数回計算する必要があることを示しています。

時間: O(n)、空間: O(n)

動的プログラミング

    public int fib(int n) {
        if(n<2){
            return n;
        }
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        for(int i=2; i<=n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }

再帰は上から下に動作し、その後バックトラッキングします。メモリ再帰は二重計算を避けるために再帰結果を保存します。これで、動的プログラミングが下から上に動作し、各ステップの結果が dp 配列に保存されます。
時間: O(n)
スペース: O(n)

また、配列の代わりに制限数値を動的に更新することもできます。これにより、特に膨大な数の要素の場合に、スペースの複雑さが節約されます。

    public int fib(int n) {
        if(n<2){
            return n;
        }
        int start = 0;
        int pre = 1;
        int res = pre;

        for(int i=2; i<=n; i++){
            res = start + pre;
            start = pre;
            pre = res;
        }
        return res;
    }

70. 階段を登る

あなたは階段を登っています。頂上に到達するには n 歩かかります。

毎回、1 段か 2 段ずつ登ることができます。いくつの異なる方法で頂上まで登ることができますか?

例 1:

入力: n = 2
出力: 2
説明: 頂上に登るには 2 つの方法があります。

1. 1 ステップ + 1 ステップ
2. 2ステップ 例 2:

入力: n = 3
出力: 3
説明: 頂上に登るには 3 つの方法があります。

1. 1 ステップ + 1 ステップ + 1 ステップ
2. 1 ステップ + 2 ステップ
3. 2 ステップ + 1 ステップ

70. 階段を登る

あなたは階段を登っています。頂上に到達するには n 歩かかります。

毎回、1 段か 2 段ずつ登ることができます。いくつの異なる方法で頂上まで登ることができますか?

例 1:

入力: n = 2
出力: 2
説明: 頂上に登るには 2 つの方法があります。

1. 1 ステップ + 1 ステップ
2. 2ステップ 例 2:

入力: n = 3
出力: 3
説明: 頂上に登るには 3 つの方法があります。

1. 1 ステップ + 1 ステップ + 1 ステップ
2. 1 ステップ + 2 ステップ
3. 2 ステップ + 1 ステップ

制約:

1 オリジナルページ

    public int climbStairs(int n) {
        if(n<3){
            return n;
        }
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        for(int i=3; i<=n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        } 
        return dp[n];       
    }

    public int climbStairs(int n) {
        if(n<3){
            return n;
        }

        int prepre = 1;
        int pre = 2;
        int res = 0;
        for(int i=3; i<=n; i++){
            res = prepre + pre;
            prepre = pre;
            pre = res;
        } 
        return res;       
    }

746. 階段を登る最小コスト

整数配列コストが与えられます。ここで、cost[i] は階段の i 番目のステップのコストです。コストを支払うと、1 段または 2 段登ることができます。

インデックス 0 のステップから開始することも、インデックス 1 のステップから開始することもできます。

フロアの最上部に到達するための最小コストを返します。

例 1:

入力: コスト = [10,15,20]
出力: 15
説明: インデックス 1 から開始します。

• 15 を支払い、2 段の階段を登って頂上に到達します。 総コストは15です。 例 2:

入力: コスト = [1,100,1,1,1,100,1,1,100,1]
出力: 6
説明: インデックス 0 から開始します。

• 1 を支払うと 2 段を登り、インデックス 2 に到達します。
• 1 を支払い、2 段登るとインデックス 4 に到達します。
• 1 を支払い、2 段登るとインデックス 6 に到達します。
• 1 を支払い、1 段登るとインデックス 7 に到達します。
• 1 を支払い、2 段登るとインデックス 9 に到達します。
• 1 を支払い、階段を 1 つ登ると頂上に到達します。 合計コストは6です。

制約:

2 0 オリジナルページ

    public int minCostClimbingStairs(int[] cost) {
        if(cost.length < 2){
            return 0;
        }

        int[] dp = new int[cost.length+1];
        dp[0] = 0;
        dp[1] = 0;

        for(int i=2; i<dp.length; i++){
            dp[i] = Math.min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);
        }
        return dp[dp.length-1];

    }
the key thing of this problem is the `init array` and `the meaning of the array` and the `Recurrence relation`

質問でインデックス 0 とインデックス 1 から開始できることが示されていることに注意してください。これは、階段の数が 2 未満の場合、コストが 0 になることを意味します。その時点から開始でき、start の動作は次のとおりです。コスト0、移動コストのみの動作。

以上がLeetCode Day動的プログラミング Part1の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。