該算法題分別是：
118. 楊輝三角。
119. 楊輝三角 II

1 [楊輝三角]

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

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

1.2 示例

1.2.1 示例 1:

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

1.2.2 示例 2:

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

1.2.3 提示:

1 <= numRows <= 30

來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/pascals-triangle
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

1.3 算法解決方法

1.3.1 算法解題思路

1.3.1.1 確定狀態(tài)

• 設(shè)dp[i][j]表示第1 + 1行，第j + 1列的數(shù)
  dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];

1.3.1.2 轉(zhuǎn)移方程

• 設(shè)dp[i][j]表示第1 + 1行，第j + 1列的數(shù)
  dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];

1.3.1.3 初始條件以及邊界情況

• 設(shè)dp[i][j]表示第1 + 1行，第j + 1列的數(shù)
  dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];

初始條件：
dp[0][0] = 1

邊界情況：
dp[i][0] = dp[i][i] = 1;

1.3.1.4 計算順序

dp[0][0]
dp[1][0]，dp[1][1]
…
dp[N - 1][0]，dp[N - 1][N - 1]

1.3.2 算法實現(xiàn)

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> dp(numRows);
        for(int i = 0; i < numRows; i++) {
            dp[i].resize(i + 1);
            dp[i][0] = dp[i][i] = 1;
        }

        for (int i = 2; i < numRows; i++) {
            for (int j = 1; j < i; j++)
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
        }

        return dp;
    }
};

2 [楊輝三角 II]

2.1 給定一個非負索引 rowIndex，返回「楊輝三角」的第 rowIndex 行。

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

2.2 示例

2.2.1 示例 1:

輸入: rowIndex = 3
輸出: [1,3,3,1]

2.2.2 示例 2:

輸入: rowIndex = 0
輸出: [1]

2.2.3 示例 3:

輸入: rowIndex = 1
輸出: [1,1]

2.2.4 提示:

0 <= rowIndex <= 33

來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/pascals-triangle-ii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2.3 算法解決方法

楊輝三角 II完全可以借助于上面的楊輝三角的解決方法去處理，不同的是要處理index和楊輝三角的關(guān)系，最后返回特定行的楊輝三角數(shù)據(jù)就可以。

2.3.1 算法解題思路

2.3.1.1 確定狀態(tài)

• 設(shè)dp[i][j]表示第1 + 1行，第j + 1列的數(shù)
  dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];

2.3.1.2 轉(zhuǎn)移方程

• 設(shè)dp[i][j]表示第1 + 1行，第j + 1列的數(shù)
  dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];

2.3.1.3 初始條件以及邊界情況

• 設(shè)dp[i][j]表示第1 + 1行，第j + 1列的數(shù)
  dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];

初始條件：
dp[0][0] = 1

邊界情況：
dp[i][0] = dp[i][i] = 1;

2.3.1.4 計算順序

dp[0][0]
dp[1][0]，dp[1][1]
…
dp[N - 1][0]，dp[N - 1][N - 1]

返回第N- 1行的數(shù)據(jù)：
dp[N - 1][0]，dp[N - 1][N - 1]文章來源地址http://www.zghlxwxcb.cn/news/detail-537488.html

2.3.2 算法實現(xiàn)

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        int numRows = rowIndex + 1;
        vector<vector<int>> dp(numRows);
        for(int i = 0; i < numRows; i++) {
            dp[i].resize(i + 1);
            dp[i][0] = dp[i][i] = 1;
        }

        for (int i = 2; i < numRows; i++) {
            for (int j = 1; j < i; j++)
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
        }

        return dp[rowIndex];

    }
};

到了這里，關(guān)于動態(tài)規(guī)劃-楊輝三角的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！