14.1 动态规划基础

若解决一个问题有很多步, 每步都有多个选择, 需要得出最优解或者求出解的数量, 那么就适合使用动态规划.

可以看出动态规划和回溯法应用场景类似, 但区别在于:

• 回溯法: 列出所有的解
• 动态规划: 给出最优解 或 解的数量

14.1.1 分治法 和 动态规划

分治法 使用递归的思路将大问题分解成小问题, 每个小问题之间没有重叠部分, 可以直接用递归代码写出算法. 例如: 快速排序.

动态规划 使用递归的思路将大问题分解成小问题, 再将小问题的解合并形成大问题的解. 关键在于找出小问题的解和大问题解的 状态转移方程 .

若小问题之间存在重叠部分, 直接使用递归代码将造成大量重复计算, 那么需要:

• 从上至下: 从大问题到小问题, 将每次小问题的解缓存下来, 避免重复计算
• 从下至上: 从解决最小问题开始, 将结果缓存下来, 不断合并小问题解逐步解决大问题.

14.1.2 问题88: 爬楼梯的最小成本

LCR 088. 使用最小花费爬楼梯

数组的每个下标作为一个阶梯，第 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 。

提示：

• 2 <= cost.length <= 1000
• 0 <= cost[i] <= 999

14.1.2.1 分析&题解

爬上楼梯可分为若干步, 每步都有两个选择, 需要求出最小消耗, 适用于动态规划.

状态转移方程

找出当前步最优解和前面若干步最优解的关系, 假设$f(i)$为第i阶向上爬的最小成本, 那么可以得出它和前若干步最优解的关系为

$f(i)=Min(f(i-2), f(i-1))+cost(i)$,

即第i-1和i-2阶的最小成本加上当前成本之和.

然后确定边界条件, 若$i<2$:

• i=1时, $f(1)=cost(1)$
• i=0时, $f(0)=cost(0)$

即$f(i)=cost(i), i<2$

递归

根据状态转移方程直接写出递归式.

直接写出的递归式时间复杂度非常糟糕, 子问题$f(i-1), f(i-2)$ 之间都重复计算了$f(i-3)$, 这样会有严重的效率问题, 且重复计算是按指数级增长的.

func minCostClimbingStairs(cost []int) int {
    length := len(cost)
    // 登顶的最小消耗
    return min(helper(cost, length-2), helper(cost, length-1))
}

// 状态转移方程
func helper(cost []int, idx int) int {
    // 递归出口
    if idx <= 1 {
        return cost[idx]
    }

    // 第idx的最小消耗
    return min(helper(cost, idx-2), helper(cost, idx-1)) + cost[idx]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

递归+缓存

避免重复计算可以将已经计算过的结果缓存下来.

使用数组dp缓存结果, 求解时若dp[i]为0, 表示未计算过才进行计算, 避免了重复的计算.

TC: O(n) SC: O(n)

func minCostClimbingStairs(cost []int) int {
    // 缓存
    dp := make([]int, len(cost))
    // 子问题
    helper(cost, dp, len(cost)-2)
    helper(cost, dp, len(cost)-1)

    return min(dp[len(cost)-2], dp[len(cost)-1])
}

func helper(cost, dp []int, idx int) {
    if idx <= 1 { // 0 or 1
        dp[idx] = cost[idx]
    } else if dp[idx] == 0 { // 还未求解
        // 求解子问题
        helper(cost, dp, idx-2)
        helper(cost, dp, idx-1)

        dp[idx] = min(dp[idx-2], dp[idx-1]) + cost[idx]
    }
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

注意:

• 最终的最优解$f(n-1)$: 取决于$f(n-2)$和$f(n-1)$, 所以要计算两个子问题, 即 helper(cost, dp, len(cost)-2)helper(cost, dp, len(cost)-1)

迭代 SC: O(n)

递归是自上而下的, 从大问题出发分解为小问题, 直到最小问题为止, 然后再将每个小问题的最优解逐渐合并成大问题的最优解.

迭代是自下而上的, 从最小问题出发, 逐渐合并成更大问题, 直到得出最大问题的最优解.

TC: O(n), SC: O(n)

func minCostClimbingStairs(cost []int) int {
    n := len(cost)
    dp := make([]int, n)
    dp[0] = cost[0]
    dp[1] = cost[1]

    for i := 2; i < n; i++ {
        dp[i] = min(dp[i-2], dp[i-1]) + cost[i]
    }

    return min(dp[n-2], dp[n-1])
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

迭代 SC: O(1)

计算$f(i)$时实际上只用得上$f(i-2), f(i-1)$的结果, 而更早的结果无需存储在缓存中.

可以将缓存大小变为2, $f(i)$存储在dp[i%2]中, 每次计算$f(i)$替换掉$f(i-2)$

此时空间复杂度就降为O(1).

func minCostClimbingStairs(cost []int) int {
    n := len(cost)
    // 缓存
    dp := make([]int, 2)
    dp[0] = cost[0]
    dp[1] = cost[1]

    for i := 2; i < n; i++ {
        a := (i-2) % 2
        b := (i-1) % 2
        dp[i%2] = min(dp[a], dp[b]) + cost[i]
    }

    return min(dp[0], dp[1])
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Reference

1. 剑指Offer（专项突破版）