前言：
动态规划通俗的说就是利用已知的历史记录来完成未知记录的计算。当我们将一个大问题分解为若干的子问题时，如果子问题之间不是独立的，那么就不适合使用递归，原因是这样会产生重复的计算，并且是爆炸性的，效率不好。
因而需要使用动态规划来避免重复的计算。
动态规划解题步骤：
1.定义dp数组所表示的含义
动态规划我们需要用一个变量来保存历史数据，或者是一维数组，或者是二维数组。我们将这个数组叫为dp(Dynamic Programming)数组。我们要明确数组元素所表示的含义，及数组下标所表示的意思。
2.确定递推公式
通俗的讲就是确定数组元素之间的关系。通常通过最后一步和子问题来确定。
3.定义初始条件及边界
有些不能由递推公式分解得出的我们要直观的给出答案。边界情况即为数组不能越界
4.确定遍历顺序（计算顺序）
按照怎样的遍历顺序进行遍历计算。根据递推公式来进行判断。
原题如下：
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
按“步”就搬：
1.定义dp数组所表示的含义
本题的问题是让我们生成杨辉三角的前numRows行，但是我们只能一行行的生成，最终结果将会组成杨辉三角。由题意dp数组为一个二维数组更加合适，因而定义第 i 行的数据为dp [ i ][0~i]。
2.确定递推公式
最后一步：假设要生成 i 行的杨辉三角，现在已经生成了第 i-1 行的杨辉三角数据。由于第 i-1 行的第0号位置+第1号位置=第 i 行的第1号位置，i-1 行的第1号位置+第2号位置=第 i 行的第2号位置……i-1 行的第i-1号位置+第i号位置=第 i 行的第 i 号位置，所以存在递推公式：dp[i][j]=dp[i-1][j-1]+dp[i-1][j]
3.定义初始条件及边界
由于dp[i][0]是不能由递推公式进行分解的所以我们要遍历将dp[i][0]的值全部设置为1；其次这这里不采用将dp数组全部初始化为0，因而dp[i][i]也是不能用递推公式分解得出的，所以将dp[i][i]的值全部设置为1；最后 j 的值是取决于 i 的值即 j <i。
4.确定遍历顺序（计算顺序）
由上分析可得该OJ题基本框架为嵌套的两层循环。根据递推公式第一层循环代表行，第二层循环代表列。再者递推公式要求解等式左边的必须知道等式右边的，而（i>i-1;j>j-1)所以第二层循环应该是从小到大的进行计算。
代码实现：
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>>dp(numRows);//开辟二维的dp数组
for(int i=0;i<numRows;i++)//遍历初始化
{
dp[i].resize(i+1);//这一步很关键
dp[i][0]=1;
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-1]+dp[i-1][j];
}
}
return dp;
}
};
我是老胡，感谢阅读！！❤️ ❤️