70-爬楼梯

LeetCode 70. Climbing Stairs

LeetCode-70

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

method

当前阶可以从i-1阶跳一格过来，也可以从i-2阶跳两格过来

int climbStairs(int n) {
    if (n <= 2) return n;
    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];
}

可以状态压缩为2个变量

int climbStairs(int n) {
    if (n <= 2) return n;
    dp0 = 1;
    dp1 = 2;
    for (int i = 3; i <= n; i++) {
        int sum = dp0 + dp1;
        dp0 = dp1;
        dp1 = sum;
    }
    return dp1;
}

改成每次可以跳m阶

就成了完全背包问题
每次可以装1件、装2件、…、装m件
类比为每次可以跳1阶、跳2阶、…、跳m阶

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

求排列数，所以先遍历背包，再遍历物品

int climbStairs(int n) {
    vector<int> dp(n + 1);
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i >= j) dp[i] += dp[i - j];
        }
    }
    return dp[n];
}

推导数学公式

f(n) = f(n-1)+f(n-2)+...+f(1)
f(n-1) = f(n-2)+f(n-2)+...+f(1)
所以
f(n) = 2 * f(n-1)   等比数列
n = 1, 2^0
n = 2, 2^1
...
n = k, 2^(k-1), 也就是1左移(k-1)位

---

LeetCode 746. Min Cost Climbing Stairs

LeetCode-746

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

Example 1:

Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.
- Pay 15 and climb two steps to reach the top.
The total cost is 15.

method

要跳到第i个台阶上需要花费cost[i]，每次可以跳一级或两级，所以状态转移方程为dp[i] = min(dp[i-1],dp[i-2]) + cost[i]

最后一级可以选择从倒数第一级或倒数第二级跳过来

int minCostClimbingStairs(vector<int>& cost) {
    vector<int> dp(cost.size());
    dp[0] = cost[0];
    dp[1] = cost[1];
    for (int i = 2; i < dp.size(); i++) {
        dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
    }
    return min(dp[dp.size() - 1], dp[dp.size() - 2]);
}

状态压缩

int minCostClimbingStairs(vector<int>& cost) {
    int dp0 = cost[0];
    int dp1 = cost[1];
    for (int i = 2; i < cost.size(); i++) {
        int res = min(dp0, dp1) + cost[i];
        dp0 = dp1;
        dp1 = res;
    }
    return min(dp0, dp1);
}