Cover image for Interview Classic 150 Questions P70 Climbing Stairs

Interview Classic 150 Questions P70 Climbing Stairs

(Updated: )
algorithm
, , ,
Timeline

Timeline

2025-11-27

init

Dynamic Programming

Problem:

P70 Climbing Stairs

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

Dynamic Programming Knapsack Problem

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];
	}
};

leetcode hot 100 rewrite

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