c++冬冬爬楼梯动态规划

冬冬爬楼梯动态规划问题是一个经典的动态规划问题，假设冬冬要爬n个台阶，每次只能爬1个或2个台阶，问他有多少种不同的爬法。

解决这个问题可以使用动态规划的思想，我们可以定义一个数组dp，其中dp[i]表示爬到第i个台阶的不同爬法数量。

那么，对于dp[i]来说，它的值可以由dp[i-1]和dp[i-2]转移得到，因为每次只能爬1个或2个台阶。所以，状态转移方程为：

dp[i] = dp[i-1] + dp[i-2]

边界条件为dp[1] = 1，dp[2] = 2，因为只有一个台阶时只有1种爬法，有两个台阶时有2种爬法。

最终，dp[n]就是冬冬爬到第n个台阶的不同爬法数量。

下面是Python实现代码：

def climbStairs(n: int) -> int:
    if n <= 2:
        return n
    dp = [0] * (n+1)
    dp[1] = 1
    dp[2] = 2
    for i in range(3, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

时间复杂度为O(n)，空间复杂度为O(n)。

相关问题

动态规划爬楼梯问题c++

好的，下面是动态规划解决爬楼梯问题的 C++ 代码：

#include <iostream>
using namespace std;

int climbStairs(int n) {
    if (n == 0 || n == 1) {
        return 1;
    }
    int nums[n + 1];
    nums[0] = 1;
    nums[1] = 1;
    for (int i = 2; i <= n; i++) {
        nums[i] = nums[i - 1] + nums[i - 2];
    }
    return nums[n];
}

int main() {
    int n = 5;
    int result = climbStairs(n);
    cout << "爬楼梯的方法数为：" << result << endl;
    return 0;
}

在这个代码中，我们通过动态规划的方法来解决爬楼梯问题。具体来说，我们先判断特殊情况，即 n=0 或 n=1 时，函数返回值为 1。对于其他情况，我们定义一个数组 nums，其中 nums[i] 表示爬 i 级楼梯的方法数。我们可以得到状态转移方程：

nums[i] = nums[i-1] + nums[i-2]

最后，返回 nums[n] 即可得到爬 n 级楼梯的方法数。

用C++编写一个动态规划做爬楼梯

下面是使用C++编写的动态规划做爬楼梯的代码：

#include <iostream>
using namespace std;

int climbStairs(int n) {
    if (n < 2) return 1; // 如果 n 小于 2，直接返回 1
    int dp[n+1]; // 定义并初始化动态规划数组
    dp[0] = 1; dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2]; // 状态转移方程
    }
    return dp[n];
}

int main() {
    int n;
    cin >> n;
    cout << climbStairs(n) << endl;
    return 0;
}

动态规划的思路是，先定义一个一维数组 dp，其中 dp[i] 表示爬 i 个台阶的不同方法数。显然，当 i=0 或 i=1 时，dp[i]=1，因为只有一种方法可以爬到第 0 级或第 1 级。对于 i>1，每次可以选择爬 1 级或 2 级，因此状态转移方程为 dp[i] = dp[i-1] + dp[i-2]，最后返回 dp[n] 即可。