案例

給定一個非負整數 numRows，生成「楊輝三角」的前 numRows 行。

在「楊輝三角」中，每個數是它左上方和右上方的數的和。

示例 1:

輸入: numRows = 5
輸出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:

輸入: numRows = 1
輸出: [[1]]

提示:

1 <= numRows <= 30

思路: 我們運用動態規劃法 我們先生成第一行 因為第一行只有一個數字那就是1 然后我們需要找到他的狀態轉移方程 也就是當前這一行的除了第一個和最后一個 都為他的上一排的前一個和第二個的和 所以要我們就得出他的狀態轉移方程 down.get[j]=up.get(j-1)+up.get(j) 最后返回list

1. 定義狀態：? 使用數組 list ，其中 first表示第一行。
2. 初始化狀態：first=1
3. 狀態轉移：? 對于 第二行 ，根據狀態轉移方程更新：
   狀態轉移方程就為down.get(j)=up.get(j-1)+up.get(j)
4. 計算順序：? 從第 2 層開始，逐步計算到第 n 層 將他依次添加到list中。
5. 返回結果：? 最終結果為 list 。

class Solution {public List<List<Integer>> generate(int numRows) {List<List<Integer>> list= new ArrayList<>();//生成第一行List<Integer> first=new ArrayList<>();first.add(1);list.add(first);//逐行生成for(int i=1;i<numRows;i++){List<Integer> down=new ArrayList<>();List<Integer> up=list.get(i-1);down.add(1);//第一個數字是1for(int j=1;j<i;j++){down.add(up.get(j-1)+up.get(j));}down.add(1);list.add(down);}return list;}
}

動態規劃法:

動態規劃法介紹:

動態規劃（Dynamic Programming，簡稱 DP）是一種用于解決多階段決策問題的算法思想，它通過將復雜問題分解為更簡單的子問題，并存儲這些子問題的解以避免重復計算，從而高效地解決問題。動態規劃通常用于優化問題，尤其是那些具有重疊子問題和最優子結構特性的問題。

核心概念

? 最優子結構：

? 一個問題的最優解可以由其子問題的最優解組合而成。換句話說，問題的解可以分解為若干個子問題的解。

? 例如，在爬樓梯問題中，到達第(n)階的方法數可以由到達第(n-1)階和第(n-2)階的方法數組合而成。

? 重疊子問題：

? 在遞歸求解過程中，同一個子問題會被多次計算。動態規劃通過存儲這些子問題的解（通常使用一個數組或哈希表），避免重復計算，從而提高效率。

? 例如，在遞歸計算斐波那契數列時，會多次計算相同的值，而動態規劃通過存儲這些值來避免重復計算。

動態規劃的優勢

? 高效性：

? 動態規劃通過存儲子問題的解，避免了重復計算，大大提高了算法的效率。時間復雜度通常為(O(n))。

? 適用性：

? 動態規劃適用于具有重疊子問題和最優子結構特性的問題，如背包問題、最長公共子序列、最短路徑問題等。

? 可擴展性：

? 動態規劃的思想可以擴展到多維問題，通過增加狀態維度來解決更復雜的問題。

動態規劃的局限性

? 空間復雜度：

? 動態規劃通常需要額外的空間來存儲子問題的解，空間復雜度可能較高。例如，爬樓梯問題的空間復雜度為(O(n))。

? 狀態轉移方程的推導：

? 動態規劃的關鍵在于推導狀態轉移方程，這需要對問題有深入的理解和分析。

? 適用范圍：

? 動態規劃只適用于具有重疊子問題和最優子結構特性的問題，對于不符合這些特性的問題，動態規劃可能不適用。

總結

動態規劃是一種強大的算法思想，通過將復雜問題分解為更簡單的子問題，并存儲這些子問題的解，避免重復計算，從而高效地解決問題。爬樓梯問題是動態規劃的經典應用之一，通過定義狀態、初始化狀態、狀態轉移和計算順序，可以高效地求解問題。