杨辉三角:动态规划

通过动态规划求解杨辉三角前n行

本质还是一维数组的动态规划。

什么是杨辉三角

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

引用一下leetcode上的杨辉三角的gif

可以看到,从第三行开始,每一行的计算结果都可以从上一行的结果中得出。我们回到动态规划的定义:

将递归算法重新写成非递归算法,并将子问题的答案系统的记录在表中

比如我们要求出杨辉三角的第四行。第四行的首尾结果肯定是1,这个不用多说。而从第四行的第i项开始,每一项都是上一行(即第三行)的第i-1项和第i+1项的和。

这里直接放leetcode题目:118. 杨辉三角的C++代码了,毕竟转成本地运行的C++代码也不难。

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> result(numRows);
        for(int i=0;i<numRows;i++)
        {
            result[i].resize(i+1);
            result[i][0]=result[i][i]=1;
            for(int j=1;j<i;j++)
            {
                if(i>=2)
                {
                    result[i][j]=result[i-1][j-1]+result[i-1][j];
                }
            }
        }
        return result;
    }
};
Subscribe
提醒
0 评论
Inline Feedbacks
View all comments
0
在此留下你的评论x