leetcode 118杨辉三角

class Solution { public: vectorvectorint generate(int numRows) { int i 0, j 0; // dp[i] 表示杨辉三角的第 i 行 vectorvectorint dp(numRows); for(i 0; i numRows; i){ // 第 i 行有 i1 个元素 dp[i].resize(i 1); // 每一行的第一个和最后一个元素都是 1 dp[i][0] dp[i][i] 1; // 计算当前行中间的元素 for(j 1; j i; j){ // 当前元素 上一行左上 上一行右上 dp[i][j] dp[i - 1][j - 1] dp[i - 1][j]; } } return dp; } };你现在重点理解这三个地方就行① 创建二维数组vectorvectorint dp(numRows);相当于先创建numRows行dp[0] dp[1] dp[2] dp[3] ...但此时每一行还没有具体的元素。② 决定每一行有几个元素dp[i].resize(i 1);例如i 0 → dp[0] 有 1 个 i 1 → dp[1] 有 2 个 i 2 → dp[2] 有 3 个 i 3 → dp[3] 有 4 个所以自然形成1 1 1 1 2 1 1 3 3 1③ 计算中间位置dp[i][j] dp[i - 1][j - 1] dp[i - 1][j];比如计算1 2 1 ↘ ↙ 3就是dp[3][1] dp[2][0] dp[2][1];也就是3 1 2最后记住这个结构dp[i] → 第 i 行 dp[i][j] → 第 i 行第 j 个元素 resize(i1) → 第 i 行开 i1 个位置 两边 → 1 中间 → 上一行左上 上一行右上所以这道题实际上就是通过每一行长度逐渐增加构造出杨辉三角再利用上一行计算当前行的中间元素。