动态规划练习（4）杨辉三角-LeetCode

水深无声 2023-09-28 22:47 8阅读 0赞

## 问题描述： ##

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

![8a3b52b4dfa53d7009411c4132c274cd.gif][]

示例 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

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/pascals-triangle

三字诀：**定—方—始**

**定：**定义数组含义，**确定最后一步完成情况**（难度：⭐⭐⭐⭐⭐），肯定子问题成立

**方：写表达式**（就那个核心方程，难度：⭐⭐⭐）

**始：**给出初始条件

总之一句话：用**数组**去完成**最后一步**得出**方程式，**给出**初始**累代码

架子一摆，开整

分析：

先把杨辉三角想象成左对齐的：

![6cd32e98f036471995d7779e802e957b.png][]

这样用坐标就好表示了

定： 定义Yang\[i\]\[j\]表示第 i 行的第 j 个数；

最后一步：求最后一行numRows的numRows个数，该行第一个和最后一以后是1，其他的第j个（2<=j<=numRows-1）数Yang\[numRows\]\[j\]都是numRows-1行对应的第j-1个与第 j数相加而得，即就是 Yang\[numRows\]\[j\] = Yang\[numRows-1\]\[j-1\] + Yang\[numRows-1\]\[j\]

numRows换成i得子问题

方：Yang\[i\]\[j\] = Yang\[i-1\]\[j-1\] + Yang\[i-1\]\[j\]

始： i 和 j 都得大于等于 2 才有意义，即每行第一个数和最后一个数得自己给出（都是1）

累代码

#include<iostream>
    //#include<cmath>
    using namespace std;
    int dp[31][31]; 
    int main(){
    	int numRows;
    	cin>>numRows;
        int Yang[31][31];
            for(int i=1;i<=numRows;i++){
                Yang[i][1]=Yang[i][i]=1;		
            } 
            for(int i=3;i<=numRows;i++){
                for(int j=2;j<i;j++){
                    Yang[i][j]=Yang[i-1][j-1]+Yang[i-1][j];
                }
            }
            cout<<"[";
            for(int i=1;i<=numRows;i++){
                cout<<"[";
                int flag=i-1;
                for(int j=1;j<=i;j++){
                    cout<<Yang[i][j];
                    if(flag--)
                        cout<<",";
    
                }
                cout<<"]";
                if(i==numRows)cout<<"]";
                else cout<<",";
            }
            return 0;
        }

结果：

![15664112fe394be9a4cb0776c4055207.png][]

[8a3b52b4dfa53d7009411c4132c274cd.gif]: https://img-blog.csdnimg.cn/img_convert/8a3b52b4dfa53d7009411c4132c274cd.gif
[6cd32e98f036471995d7779e802e957b.png]: https://img-blog.csdnimg.cn/6cd32e98f036471995d7779e802e957b.png
[15664112fe394be9a4cb0776c4055207.png]: https://img-blog.csdnimg.cn/15664112fe394be9a4cb0776c4055207.png