每日算法4.18之动态规划

力扣70爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶
   示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提示：

1 <= n <= 45

题目分析

一共有n阶楼梯，一次能爬1个或2个台阶，求有多少种方法能爬上楼顶

解题思路

爬第n次楼梯时，第n-1次爬楼梯一定走了1阶或2阶楼梯
我们用f(x)代表爬到第x阶楼梯的方案个数，所以f(x)=f(x-1)+f(x-2)
理解：因为一次只能爬1个或2个台阶，所以爬第x阶台阶方案的种类来自于爬第x-1阶台阶方案数与爬第x-2阶台阶方案数之和，换句话说等于迈一步方案数和迈2步方案数之和

代码实现

class Solution {
public:
    int climbStairs(int n) {
        int p=0,q=0,r=1;
        for(int i=0;i<n;i++)
        {
            p=q;
            q=r;
            r=p+q;
        }
        return r;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

力扣118杨辉三角

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

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

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

题目分析

输出前n行的杨辉三角

解题思路

根据第i行j列的数等于第i-1行j列与第i-1行j-1列之和可列出公式，因为最左边一列的j-1列都为0，所以可以保证都为1，而最右边一列的j列都为0，同样也可以保证
注意：力扣的官方题解给的第二层for循环进入条件为j<=n，但是我们可以发现每一层的数字个数都小于等于层数，我们可以将其改为j<=i,大大减少运行时间

代码实现

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>>gen;
        int dp[32][32]={0};
        dp[0][0]=1;
        for(int i=1;i<=numRows;i++){
            vector<int>temp;
            for(int j=1;j<=i;j++){
                dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
                if(dp[i][j]){
                    temp.push_back(dp[i][j]);
                }
            }
            gen.push_back(temp);
        }
        return gen;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19