什么是動態規劃

動態規劃是一種通過將原問題分解為相對簡單的子問題來解決復雜問題的方法。基本思想是遞歸地將一個復雜的問題劃分為許多更簡單的子問題，存儲這些子問題的每個子問題的解，并最終將存儲的答案用于解決原始問題。通過緩存子問題的解，動態規劃有時可以避免指數級的浪費。它通常用于優化問題，其中需要找到最佳解決方案。動態規劃算法通常用于解決具有重疊子問題和最優子結構性質的問題。

• 重疊子問題：原問題可以被分解為相同的子問題。這意味著在解決原問題時，我們可能多次解決相同的子問題。
• 最優子結構：問題的最優解可以通過其子問題的最優解來求解。

通常，使用動態規劃解決問題的步驟包括以下幾個方面：

• 定義子問題：將原問題分解為子問題。
• 解決子問題：解決子問題并將結果存儲起來，通常使用數組或類似的數據結構來存儲子問題的解，以避免重復計算。
• 合并子問題的解：利用子問題的解構建原問題的解。
• 遞歸或迭代：通常使用遞歸或迭代的方式來解決問題。

斐波那契數組相關題目

斐波那契數組是典型的動態規劃問題，可以從存儲的子問題答案擴展到要求解的大問題。

509. 斐波那契數 Easy

509. 斐波那契數

斐波那契數 （通常用 F(n) 表示）形成的序列稱為 斐波那契數列 。該數列由 0 和 1 開始，后面的每一項數字都是前面兩項數字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
給定 n ，請計算 F(n) 。

其實可以直接用一個數組，dp[i]就對應F(i)，但實際上我們并不需要整個數組，只需要F(n)，而F(n)只和F(n-1)和F(n-2)相關，因此直接用兩個變量存儲即可。更新過程就是F(n) = F(n - 1) + F(n - 2)。Java代碼如下：

class Solution {public int fib(int n) {if(n <= 1)return n;int f0 =0, f1 = 1;for(int i = 2; i <= n; i++){int cur = f0 + f1;f0 = f1;f1 = cur;}return f1;}
}

1137. 第 N 個泰波那契數 Easy

1137. 第 N 個泰波那契數

泰波那契序列 Tn 定義如下：
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的條件下 Tn+3 = Tn + Tn+1 + Tn+2
給你整數 n，請返回第 n 個泰波那契數 Tn 的值。

這個和上面的斐波那契基本一樣，只是當前狀態由前面三個狀態決定，而不是前面兩個。用三個變量分別存儲Tn、Tn+1、Tn+2，按照 Tn+3 = Tn + Tn+1 + Tn+2逐步更新即可。 Java代碼如下：

    public int tribonacci(int n) {if(n <= 1)return n;if (n == 2)return 1;int f0 = 0, f1 = 1, f2 = 1;for(int i = 3; i <= n; i++){int cur = f0 + f1 + f2;f0 = f1;f1 = f2;f2 = cur;}return f2;}
}

楊輝三角

118. 楊輝三角 Easy

118. 楊輝三角

給定一個非負整數 numRows，生成「楊輝三角」的前 numRows 行。
在「楊輝三角」中，每個數是它左上方和右上方的數的和。

其實斐波那契和楊輝三角，都是數學里面學過的，更新過程已經很清晰了。 上面的圖這個三角形，如果變成數組左下角直角的形式，對于每一行，dp[i][j] = dp[i-1][j-1] + dp[i-1][j]。Java代碼如下：

class Solution {public List<List<Integer>> generate(int numRows) {List<List<Integer>> triangle = new ArrayList<>();   for(int i = 0; i < numRows; i++){List<Integer> newRow = new ArrayList<>();            for(int j = 0; j <= i; j++){if(j==0 || j==i)newRow.add(1);elsenewRow.add(triangle.get(i-1).get(j) + triangle.get(i-1).get(j-1));}           triangle.add(newRow);}return triangle;        }
}

爬樓梯相關題目

70. 爬樓梯 Easy

70. 爬樓梯

假設你正在爬樓梯。需要 n 階你才能到達樓頂。
每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？

根據題目，到第n階臺階，可以從n-1跨一步到；可以從n-2跨兩步到。因此動態規劃的狀態轉移：dp[n] = dp[n-1] + dp[n-2]。實際上只需要存儲dp[n-1]和dp[n-2]這兩個變量即可。Java代碼如下：

class Solution {public int climbStairs(int n) {if(n <=2 )return n;int stair1 =1, stair2 = 2;for(int i = 3; i <= n; i++){int cur = stair1 + stair2;stair1 = stair2;stair2 = cur;}return stair2;    }
}

746. 使用最小花費爬樓梯 Easy

746. 使用最小花費爬樓梯

給你一個整數數組 cost ，其中 cost[i] 是從樓梯第 i 個臺階向上爬需要支付的費用。一旦你支付此費用，即可選擇向上爬一個或者兩個臺階。
你可以選擇從下標為 0 或下標為 1 的臺階開始爬樓梯。
請你計算并返回達到樓梯頂部的最低花費。
示例 1：
輸入：cost = [10,15,20]
輸出：15
解釋：你將從下標為 1 的臺階開始。支付 15 ，向上爬兩個臺階，到達樓梯頂部。總花費為 15 。

上一個題目是直接求方法總和，這個題目是最小最大問題。 但本質上兩個題一樣的，因此到當前第i個臺階的代價，取決與i-1和i-2。因為在i-1個臺階上付出cost[i-1]的費用，選擇向上一個臺階就到了第i階；同樣在第i-2個臺階上付出cost[i-2]的費用，選擇向上兩個臺階就到了第i個臺階。因為是最小值，因此dp[i] = min(dp[i-2] + cost[i-2], dp[i-1] + cost[i-1])。由于只和dp[i-1]、dp[i-2]兩個狀態相關，因此可以優化成只用兩個變量存儲，Java代碼如下：

class Solution {public int minCostClimbingStairs(int[] cost) {int n = cost.length;if(n == 2)return Math.min(cost[0],cost[1]);int minCost1 = 0, minCost2 = 0;for(int i = 2; i <= n ; i++){int newCost = Math.min(minCost1 + cost[i-2], minCost2 + cost[i-1]);minCost1 = minCost2;minCost2 = newCost;}return minCost2;}
}