【必备算法】动态规划：LeetCode题（一）：70.爬楼梯，746. 使用最小花费爬楼梯

70.爬楼梯¹

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

解法一：分治（超时）

• 思路：分解模型（==> 求爬到每个楼梯有多少种爬法）。递推公式，f(n) = f(n-1) + f(n-2)。
• 复杂度
  • Time：O(2^n)，递归树有2^n个节点，每个节点都要计算
  • Space：O(2^n)

public int climbStairs(int n) {
        return climb(n);
}

public int climb(int n) {
    if (n == 1 || n == 0) return 1;
    return climb(n-1) + climb(n-2);
}

由于递归的重复计算过多，导致递归树重复节点过多，故而超时。

解法二：记忆递归

• 思路：空间换时间，引入一个数组记录每次产生的中间结果。后面在每次调用函数时如果数组中有，就直接返回，若没有则计算并放入数组。
• 复杂度：
  • Time：O(n)，此时递归树只有n个节点，因为不存在重复计算
  • Space：O(n)

public int climbStairs(int n) {
    	// 定义数组，保存中间结果
        int[] tmp = new int[n + 1];
        return climb2(n,tmp);
}

public int climb2(int n, int[] tmp) {
        if (n == 1 || n == 0) return 1;
    	// 若数组中有就直接返回
        if (tmp[n] != 0) return tmp[n];
        // 没有，计算并放入数组    
        tmp[n] = climb2(n - 1,tmp) + climb2(n - 2,tmp);
        return tmp[n];
}

解法三：动态规划

• 分解模型&&重复子问题。
  • 状态数组：d[i]。到每个台阶i有多少种走法。
  • 初始状态：d[0]=1, d[1]=1。上第零级（d[0]本质是一个辅助变量）和第一级的走法确定。

    注意，与斐波那契数列的区别，本题是 1,2,3,5；斐波那契是 0,1,1,2,3,5

  • 状态方程：d[i] = d[i-1] + d[i-2]。由上面递推公式就可以得到。
  • 最终状态：d[n]
• 复杂度
  • Time：O(n)
  • Space：O(n)，需要一个状态数组

public int climbStairs(int n) {
		// 状态数组。注意这里大小是n+1
        int[] d = new int[n+1];
        // 初始状态
        d[0] = 1; d[1] = 1;
        // 状态递推
        for (int i = 2; i <= n; i++) 
            d[i] = d[i-1] + d[i-2];
        // 最终状态
        return d[n];
    }

不难发现，在状态递推时始终用到的变量只有两个（d[i],d[i-1],d[i-2]），所以我们可以把状态数组进行优化，优化成三个状态变量(f1,f2,f3)。从而，时空间复杂度从O(n)降到O(1)。

// Space：O(1)
public int climbStairs(int n) {
       int f1 = 0 , f2 = 1 ,f3 = 0;
       for (int i = 0; i < n; i++) {
           f3 = f2 + f1;
           f1 = f2;
           f2 = f3;
       } 
       return f3;
}

746. 使用最小花费爬楼梯¹

数组的每个索引做为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 cost[i](索引从0开始)。

每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。

您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。

示例 1:

输入: cost = [10, 15, 20]
输出: 15
解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。

示例 2:

输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出: 6
解释: 最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。

注意：

1. cost 的长度将会在 [2, 1000]。
2. 每一个 cost[i] 将会是一个Integer类型，范围为 [0, 999]。

解法：动态规划

• 思路：分解模型&&重复子问题（==>求上到每一级台阶的最小花费）。递推公式，f(n) = min(f(n-1), f(n-2)) + cost[n]。
  • 状态数组：d[i]。爬到第 i 层的最小花费。
  • 初始状态：d[0]=cost[0], d[1]=cost[1]。注意，这里dp[1] = cost[1]，不是min（cost[1],cost[0])。
  • 状态方程：d[i] = cost[i] + min(d[i - 1], d[i - 2])。没什么说的了。
  • 最终状态：min(d[len-1], d[len-2]。对于跨到第n层，可以从d[n-1]跨一步，或者从d[n-2]跨两步，取小的。
• 复杂度：
  • Time：O(n)
  • Space：O(n)

public int minCostClimbingStairs(int[] cost) {
        // 状态数组
        int[] dp = new int[cost.length];
        // 状态初始
        dp[0] = cost[0]; dp[1] = cost[1];
        // 状态递推
        for (int i = 2; i < cost.length; i++) {
            dp[i] = cost[i] + Math.min(dp[i - 1], dp[i - 2]);
        }
    	// 最终状态。返回的是min（dp[len - 1], dp[len - 2])，不是直接返回
        return Math.min(dp[cost.length - 1], dp[cost.length - 2]);
    }

从上面代码可以看出，在状态递推的过程中，只会用到两个变量（d[i]-1和d[i-2]），所以可以将状态数组优化成两个状态变量（pre1, pre2）。

// Space：O(1)
public int minCostClimbingStairs(int[] cost) {
        int pre1 = cost[1], pre2 = cost[0];
        for (int i = 2; i < cost.length; i++) {
            int tmp = pre1;
            pre1 = cost[i] + Math.min(pre1, pre2);
            pre2 = tmp;
        }
        return Math.min(pre1, pre2);
    }