时间轴

2025-11-27

init

题目：

P70 爬楼梯

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

动态规划背包问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#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];
	}
};