面试经典150题 P70 爬楼梯

---

时间轴

时间轴

2025-11-27

init

动态规划

---

题目：

P70 爬楼梯

https://leetcode.cn/problems/climbing-stairs/description/?envType=study-plan-v2&envId=top-interview-150

动态规划背包问题

#include <vector>
using std::vector;
class Solution {
    public:
	int climbStairs(int n)
	{
		// dp[n]=dp[n-1]+dp[n-2]
		// dp[1]=1
		// dp[2]=2
		// dp[i]=dp[i-1]+dp[i-2]
		if (n == 1) {
			return 1;
		}
		vector<int> dp(n + 1);
		dp[1] = 1;
		dp[2] = 2;
		for (int i = 3; i <= n; i++) {
			dp[i] = dp[i - 1] + dp[i - 2];
		}
		return dp[n];
	}
};

leetcode hot 100 rewrite

#include <vector>
using std::vector;

class Solution {
    public:
        int climbStairs(int n)
        {
                int i;
                vector<int> dp(n + 1);
                if (n == 1)
                        return 1;
                dp[1] = 1;
                dp[2] = 2;

                for (i = 3; i <= n; i++)
                        dp[i] = dp[i - 1] + dp[i - 2];

                return dp[n];
        }
};