算法练习：常用算法设计思想之四——动态规划(Dynamic Programming)

[ShannonChenCHN]

题目列表

• 斐波那契同类问题
  • 剑指 Offer 10- I. 斐波那契数列⭐️ ✅
  • 70. 爬楼梯⭐️ ✅
• 子序列/子数组/子串
  • 300. 最长递增子序列（难度中等）⭐️⭐️ ✅
  • 152. 乘积最大子数组 ✅
  • 53. 最大子序和（注：本题同剑指 Offer 42. 连续子数组的最大和）⭐️ ✅
  • 1143. 最长公共子序列（难度中等）⭐️ ✅
  • 5. 最长回文子串（难度中等）⭐️ ✅
  • 392. 判断子序列
• 股票问题系列通解（转载翻译）⭐️
  • 121. 买卖股票的最佳时机（注：本题同剑指 Offer 63. 股票的最大利润）✅
  • 122. 买卖股票的最佳时机 II ✅
  • 123. 买卖股票的最佳时机 III（难度困难）
  • 188. 买卖股票的最佳时机 IV（难度困难）
  • 309. 最佳买卖股票时机含冷冻期（难度中等）
  • 714. 买卖股票的最佳时机含手续费（难度中等）
• 路径条数和路径和的问题
  • 120. 三角形最小路径和（难度中等）⭐️⭐️ ✅
  • 64. 最小路径和（难度中等）⭐️⭐️ ✅
  • 62. 不同路径（难度中等）
  • 63. 不同路径 II（难度中等）
  • 剑指 Offer 47. 礼物的最大价值（难度中等）
• 一维数组+最优解
  • 322. 零钱兑换（难度中等）⭐️⭐️ ✅
  • 198. 打家劫舍（难度中等）⭐️ ✅
  • 剑指 Offer 14- I. 剪绳子（难度中等）
  • 343. 整数拆分（难度中等）
• 二维数组+最终解
  • 10. 正则表达式匹配（难度困难）（注：本题同剑指 Offer 19. 正则表达式匹配）⭐️ ✅
  • 72. 编辑距离（难度困难）⭐️⭐️ ✅
• 42. 接雨水（难度困难）⭐️ ✅
• 0-1 背包问题 ⭐️
• 338. 比特位计数（难度中等）

总结

• 看到题目后，首先要分析能不能用动态规划解，一般先试试用暴力穷举法能不能做出来，然后再看是否符合”一个模型三个特征“
• 绝大多数动态规划的问题都是一维和二维的，只有极少数会涉及到三维(比如123. 买卖股票的最佳时机 III)
• 动态规划解题五步曲
  • 状态定义：这个往往跟题目中要求的最优解有关，一般是直接相关，也有个别情况并不是直接相关，比如 300. 最长递增子序列
  • 状态转移方程：写状态转移方程时需要考虑到遍历的维度，也就是状态是怎么转移的，一般都是比较简单的 i j 递增，但是有些特殊情况也要具体分析，比如 5. 最长回文子串 这一题
  • 状态初始化：写完状态转移方程之后，还需要考虑到一些边界条件，也就是状态初始化
  • 返回结果
  • 空间优化：AC 之后，再看看是否有空间优化的可能，一般情况下二维数组可以优化成一维数组(画矩阵表)，一维数组可以优化成两个非集合类型的变量
• 写完之后，一定要自己跑几个 case 验证一下，注意各种边界条件
• 字符串比较求最优解这类问题一般都可以用动态规划求解，值得注意的是，一般定义状态时会把dp[i][j]表示前 i, j 个字符串的状态，但是在遍历字符串时一定要记得前 i 个字符串的最后一个字符是第 i-1 位而不是第 i 位。比如 10. 正则表达式匹配

[ShannonChenCHN]

理论知识：动态规划(Dynamic Programming)

1. 什么是动态规划？
2. 动态规划适合解决什么样的问题？
3. 动态规划的解题套路
4. 动态规划 vs 分治 vs 回溯 vs 贪⼼

一、什么是动态规划？

二、动态规划适合解决什么样的问题？

动态规划适合解决的问题具备“一个模型三个特征”：

• 多阶段决策最优解模型
• 三个特征
  • 最优子结构：后面阶段的状态可以通过前面阶段的状态推导出来
  • 无后效性：当前阶段状态只跟上一阶段的状态有关，不受后面的阶段决策影响
  • 重复子问题：不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。比如斐波那契数列中，计算 f(4) = f(3) + f(2) 时，这其中计算 f(3) 时又会把 f(2) 重复计算一遍

我们一般是用动态规划来解决最优问题。而解决问题的过程，需要经历多个决策阶段。每个决策阶段都对应着一组状态。然后我们寻找一组决策序列，经过这组决策序列，能够产生最终期望求解的最优值。

典型问题：

• 0-1 背包问题
• 0-1 背包问题升级版
• 120. 三角形最小路径和
• 64. 最小路径和
• 322. 零钱兑换
• 计算编辑距离（72. 编辑距离）
  • 莱文斯坦距离（Levenshtein distance）
  • 最长公共子串长度（Longest common substring length）
• 300. 最长递增子序列

三、动态规划的解题套路

1. 状态定义
2. 动态转移方程
3. 初始状态
4. 得到最终结果
5. 空间优化(可选)

四、动态规划 vs 分治 vs 回溯 vs 贪⼼

详见 极客时间专栏：数据结构和算法之美。

参考

• 极客时间专栏：算法通关面试40讲
• 极客时间专栏：数据结构和算法之美
• 《剑指Offer》

[ShannonChenCHN]

70. 爬楼梯

2021.04.04 04:40 pm ~ 05:50 pm

参考题解：

• https://time.geekbang.org/course/detail/100019701-69779
• https://leetcode.com/problems/climbing-stairs/discuss/25299/Basically-it's-a-fibonacci.
• https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-by-leetcode-solution/

这个爬楼梯问题的问题模型跟斐波那契数列问题是一样的。

解法一：递归+记忆化

递推公式：

f(1) = 1; 
f(2) = 2;
f(n) = f(n-1) + f(n-2)

时间复杂度：O(n)
空间复杂度：O(n)

class Solution {
    var mem: [Int] = [Int]()
    func climbStairs(_ n: Int) -> Int {
        guard n > 2 else {   
            return n
        }
        mem = Array(repeating: 0, count: n+1)
        mem[1] = 1
        mem[2] = 2
        return _recursive(n)
    }

    func _recursive(_ n: Int) -> Int {
        if mem[n] == 0 {
            mem[n] = _recursive(n-1) + _recursive(n-2)
        }
        
        return mem[n]
    }
}

解法二：动态规划

1. 状态定义： 设 dp 为大小 n 的一维数组，其中 dp[i] 的值表示到 i+1 级台阶的走法个数
2. 动态转移方程： 根据递推公式 f(n) = f(n-1) + f(n-2)，得到状态转移方程：dp[i] = dp[i-1] + dp[i-2]
3. 初始状态：dp[0] = 1; dp[1] = 2;
4. 返回结果： dp[n-1]

空间复杂度：O(n)
时间复杂度：O(n)

class Solution {
    func climbStairs(_ n: Int) -> Int {
        guard n > 2 else {
            return n
        }
        var dp: [Int] = Array(repeating: 0, count: n)
        dp[0] = 1
        dp[1] = 2
        for i in 2..<n {
            dp[i] = dp[i-1] + dp[i-2]
        }
        return dp[n-1]
    }
}

5. 空间优化： 因为我们只需要知道 n 级台阶的走法，而 f(n) 只跟 f(n-1) 和 f(n-2) 相关，所以中间的过程可以不用一直记录。

空间复杂度：O(1)
时间复杂度：O(n)

class Solution {
    func climbStairs(_ n: Int) -> Int {
        guard n > 2 else {
            return n
        }
        var fn1 = 1
        var fn2 = 2
        var fn3 = 0
        for i in 3...n {
            fn3 = fn1 + fn2
            fn1 = fn2
            fn2 = fn3
        }
        return fn3
    }
}

[ShannonChenCHN]

剑指 Offer 10- I. 斐波那契数列

2021.04.04 06:05 pm ~ 06:15 pm

解法一：递归+记忆化

解法二：动态规划

1. 状态定义： 设 dp 为大小 n 的一维数组，其中 dp[i] 的值表示 fib(i) 的值
2. 动态转移方程： 根据递推公式 f(n) = f(n-1) + f(n-2)，得到状态转移方程：dp[i] = dp[i-1] + dp[i-2]
3. 初始状态：dp[0] = 0; dp[1] = 1;
4. 返回结果： dp[n]

时间复杂度: O(n)
空间复杂度: O(n)

class Solution {
    func fib(_ n: Int) -> Int {
        guard n > 1 else {
            return n
        }
        var dp: [Int] = Array(repeating: 0, count: n+1)
        dp[0] = 0
        dp[1] = 1
        for i in 2...n {
            dp[i] = (dp[i-1] + dp[i-2]) % 1000000007
        }
        return dp[n]
    }
}

5. 空间优化： 因为我们只需要知道 fib(n) 的值，而 fib(n) 只跟 fib(n-1) 和 fib(n-2) 相关，所以中间的过程可以不用一直记录。

时间复杂度: O(n)
空间复杂度: O(1)

class Solution {
    func fib(_ n: Int) -> Int {
        guard n > 1 else {
            return n
        }
        var fn0 = 0
        var fn1 = 1
        var fn2 = fn0 + fn1
        for i in 2...n {
            fn2 = (fn0 + fn1) % 1000000007
            fn0 = fn1
            fn1 = fn2
        }
        return fn2
    }
}

[ShannonChenCHN]

120. 三角形最小路径和（难度中等）

2021.04.04 09:00 pm ~ 11:00 pm

参考题解：

• https://time.geekbang.org/course/detail/100019701-69780
• https://leetcode.com/problems/triangle/discuss/38730/DP-Solution-for-Triangle
• https://leetcode-cn.com/problems/triangle/solution/di-gui-ji-yi-hua-dp-bi-xu-miao-dong-by-sweetiee/

分析

   2
  3 4
 6 5 7
4 1 8 3

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

2 下面有 3 和 4，所以最小路径是 2 + min(minPath(3), minPath(4))，以此类推。

解法一：递归+记忆化(自顶向下)

递推公式： minpath(row, i) = triangle[row][i] + min(minpath(row+1, i), minpath(row+1, i+1))
终止条件： row < triangle.count, i < triangle[row].count

时间复杂度： O(n^2)
空间复杂度： O(n^2)

class Solution {
    var mem: [[Int]] = [[Int]]()
    func minimumTotal(_ triangle: [[Int]]) -> Int {
        let row = Array(repeating: Int.max, count: triangle.last!.count)
        mem = Array(repeating: row, count: triangle.count)
        return minPath(triangle, 0, 0)
    }

    func minPath(_ triangle: [[Int]], _ row: Int, _ i: Int) -> Int {
        guard row < triangle.count && i < triangle[row].count else {
            return 0
        }
        
        if mem[row][i] != Int.max {
            return mem[row][i]
        }

        mem[row][i] = triangle[row][i] + min(minPath(triangle, row+1, i), minPath(triangle, row+1, i+1))
        return mem[row][i]
    }
}

解法二：动态规划(自底向上)

1. 状态定义： minpath[row][i] 为第 row 行，第 i 个节结点的最小路径和
2. 状态转移方程： minpath[row][i] = triangle[row][i] + min(minpath[row+1][i], minpath[row+1][i+1])
3. 初始状态： 自底向上，minpath[triangle.count-1][i] = triangle[triangle.count-1][i]
4. 返回结果： minpath[0][0]

时间复杂度： O(n^2)
空间复杂度： O(n^2)

class Solution {

    func minimumTotal(_ triangle: [[Int]]) -> Int {
        let subMinpath: [Int] = [Int](repeating: 0, count: triangle.count)
        var minpath: [[Int]] = [[Int]](repeating: subMinpath, count: triangle.count)

        // 状态初始化(边界条件)：最后一行
        for i in 0..<minpath.last!.count {
            minpath[minpath.count-1][i] = triangle[triangle.count-1][i]
        }
        
        for row in stride(from: triangle.count - 2, through: 0, by: -1) { // 从倒数第2行开始
            for i in 0..<triangle[row].count {
                minpath[row][i] = triangle[row][i] + min(minpath[row+1][i], minpath[row+1][i+1])
            }
        }

        return minpath[0][0]
    }
}

空间优化(结合画图)

因为我们在计算完第 k 层的结点的最小路径和后，第 k+1 层的记录就没用了，而且第 k 层第 i 个结点的最小路径是由第 k+1 层第 i 个结点和第 i+1 个结点得来的，所以我们可以把记录状态的数组改成一维数组。

以 row == 2, i == 0 为例：

1. 状态定义： minpath[i] 为当前行第 i 个节结点的最小路径和
2. 状态转移方程： minpath[i] = triangle[row][i] + min(minpath[i], minpath[i+1])
3. 初始状态： 自底向上，minpath[i] = triangle[triangle.count-1][i]
4. 返回结果： minpath[0]

时间复杂度： O(n^2)
空间复杂度： O(n)

class Solution {

    func minimumTotal(_ triangle: [[Int]]) -> Int {
        var minpath: [Int] = [Int](repeating: 0, count: triangle.count)
// 状态初始化(边界条件)：最后一行
        for i in 0..<minpath.count {
            minpath[i] = triangle[triangle.count-1][i]
        }

        for row in stride(from: triangle.count - 2, through: 0, by: -1) { // 从倒数第2行开始
            for i in 0..<triangle[row].count {
                minpath[i] = triangle[row][i] + min(minpath[i], minpath[i+1])
            }
        }

        return minpath[0]
    }
}

[ShannonChenCHN]

300. 最长递增子序列（难度中等）

2021.04.05 10:00 am ~ 12:00 am

示例：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

参考题解：

• https://time.geekbang.org/course/detail/100019701-69783
• https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/dong-tai-gui-hua-er-fen-cha-zhao-tan-xin-suan-fa-p/

注意：这里首先要搞清楚子数组/子串和子序列的区别，这个题解讲的很清楚，可以参考一下。

• 子序列（subsequence）：子序列并不要求连续，例如：序列 [4, 6, 5] 是 [1, 2, 4, 3, 7, 6, 5] 的一个子序列；
• 子串/子数组（substring、subarray）：子串一定是原始字符串的连续子串。

解法一：暴力法

时间复杂度：O(n*2^n)

解法二：动态规划

这道题满足动态规划问题的“一个模型三个特征”，因为 nums 中任一个元素选中后，以它结尾的最长严格递增子序列的长度，都取决于位于它之前的更小元素的最长严格递增子序列的长度

1. 状态定义：dp[tail] 为以 nums[tail] 结尾的最长严格递增子序列的长度
2. 状态转移方程：dp[tail] = 1 + max(dp[i] for i in 0..<tail if nums[i] < nums[tail])
3. 初始状态：dp[0] = 1
4. 最终结果：max(dp[i] in dp)
5. 空间优化：需要注意的是，dp[tail] 跟它前面的多个元素的 dp[i] 有关，所以空间没法再优化了

时间复杂度：O(n^2)
空间复杂度：O(n)

class Solution {

    func lengthOfLIS(_ nums: [Int]) -> Int {
        guard nums.count > 1 else {
            return 1
        }
        var dp: [Int] = [Int](repeating: 1, count: nums.count)
        for tail in 1..<nums.count {
            for i in 0..<tail {
                if nums[i] < nums[tail] {
                    dp[tail] = max(dp[i]+1, dp[tail])
                }
            }
        }
        var maxLength = 1
        for length in dp {
            maxLength = max(length, maxLength)
        }
        return maxLength
    }
}

解法三：二分查找法

参考题解：

• https://time.geekbang.org/course/detail/100019701-69783
• https://leetcode.com/problems/longest-increasing-subsequence/discuss/74824/JavaPython-Binary-search-O(nlogn)-time-with-explanation

TODO

[ShannonChenCHN]

152. 乘积最大子数组（难度中等）

2021.04.05 08:00 pm ~ 09:00 pm, 09:40 pm ~ 10:45 pm

注：做这道题之前建议先做一下 53. 最大子序和。

示例：

输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

解法一：暴力解法(递归)

解法二：动态规划

参考题解：

• https://time.geekbang.org/course/detail/100019701-69781
• https://leetcode-cn.com/problems/maximum-product-subarray/solution/dong-tai-gui-hua-li-jie-wu-hou-xiao-xing-by-liweiw/

1. 定义状态： 与 53 题的区别在于这里需要考虑负数的情况，所以对于每个元素需要定义两种状态，dpMax[i] 和 dpMin[i] 分别表示以 nums[i] 结尾的子数组的最大乘积和最小乘积（这两个乘积值的正负是不确定的）。

2. 状态转移方程：

dpMax[i] = 0 if nums[i] == 0
dpMin[i] = 0 if nums[i] == 0

dpMax[i] = max(nums[i], dpMax[i-1]*nums[i]) if nums[i] > 0 // dpMax[i-1] 有可能为负数
dpMin[i] = min(nums[i], dpMin[i-1]*nums[i]) if nums[i] > 0 // dpMax[i-1] 有可能为正数

dpMax[i] = max(nums[i], dpMin[i-1]*nums[i]) if nums[i] < 0 // dpMax[i-1] 有可能为正数
dpMin[i] = min(nums[i], dpMax[i-1]*nums[i]) if nums[i] < 0 // dpMax[i-1] 有可能为负数

3. 初始状态： 因为题目要求子数组至少包含一个数字，dpMax[0] = nums[i], dpMin[0] = nums[i]

4. 返回结果： max(dpMax)

class Solution {
    func maxProduct(_ nums: [Int]) -> Int {
        guard nums.count > 1 else {
            return nums[0]
        }
        var result = nums[0]
        var dpMax: [Int] = [Int](repeating: 0, count: nums.count)
        var dpMin: [Int] = [Int](repeating: 0, count: nums.count)

        dpMax[0] = nums[0]
        dpMin[0] = nums[0]
        for i in 1..<nums.count {
            if nums[i] > 0 {
                dpMax[i] = max(nums[i], dpMax[i-1]*nums[i])
                dpMin[i] = min(nums[i], dpMin[i-1]*nums[i])
            } else if nums[i] < 0 {
                dpMax[i] = max(nums[i], dpMin[i-1]*nums[i])
                dpMin[i] = min(nums[i], dpMax[i-1]*nums[i])
            } else {
                dpMax[i] = 0
                dpMin[i] = 0
            }
            result = max(dpMax[i], result)
        }
        return result
    }
}

5. 空间优化： 跟第 53 题同理，因为 dpMax[i] 和 dpMin[i] 分别只与 dpMax[i-1] 和 dpMin[i-1] 有关，所以我们可以只用两个 Int 变量将 dpMax[i-1] 和 dpMin[i-1] 记录下来即可。

class Solution {
    func maxProduct(_ nums: [Int]) -> Int {
        guard nums.count > 1 else {
            return nums[0]
        }
        var result = nums[0]
        var curMax = nums[0]
        var curMin = nums[0]
        for i in 1..<nums.count {
            if nums[i] > 0 {
                curMax = max(nums[i], curMax*nums[i])
                curMin = min(nums[i], curMin*nums[i])
            } else if nums[i] < 0 {
                let prevMax = curMax
                curMax = max(nums[i], curMin*nums[i])
                curMin = min(nums[i], prevMax*nums[i])
            } else {
                curMax = 0
                curMin = 0
            }
            result = max(curMax, result)
        }
        return result
    }
}

[ShannonChenCHN]

53. 最大子序和

2021.04.05 09:00 pm ~ 09:35 pm

示例：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 

解法一：暴力解法

解法二：动态规划

1. 状态定义：dp[i] 以 nums[i] 结尾的子数组的最大子序和
2. 状态转移方程：dp[i] = max(nums[i], dp[i-1] + nums[i])
3. 初始状态：dp[0] = nums[0]
4. 最终结果：max(dp[i] in dp)

时间复杂度：O(n)
空间复杂度：O(n)

class Solution {
    func maxSubArray(_ nums: [Int]) -> Int {
        guard nums.count > 1 else {
            return nums[0]
        }
        var dp: [Int] = [Int](repeating: 0, count: nums.count)
        dp[0] = nums[0]
        for i in 1..<nums.count {
            dp[i] = max(nums[i], dp[i-1] + nums[i])
        }

        var maxSum = nums[0]
        for sum in dp {
            maxSum = max(maxSum, sum)
        }

        return maxSum
    }
}

5. 空间优化：因为 dp[i] 只与 dp[i-1] 有关，所以我们可以只用一个 Int 变量 prevSum 将 dp[i-1] 的记录下来即可。
时间复杂度：O(n)
空间复杂度：O(1)

class Solution {
    func maxSubArray(_ nums: [Int]) -> Int {
        guard nums.count > 1 else {
            return nums[0]
        }
        var prevMaxSum = nums[0]
        var maxSum = prevMaxSum
        for i in 1..<nums.count {
            prevMaxSum = max(prevMaxSum+nums[i], nums[i])
            maxSum = max(maxSum, prevMaxSum)
        }

        return maxSum
    }
}

解法三：分治法（线段树）

[ShannonChenCHN]

322. 零钱兑换（难度中等）

2021.04.11 10:00 am ~ 12:30 am

示例：

输入：coins = [1, 2, 5], amount = 11
输出：最少硬币个数是 3 
解释：11 = 5 + 5 + 1

参考题解：

• https://time.geekbang.org/course/detail/100019701-69784
• https://leetcode-cn.com/problems/coin-change/solution/javadi-gui-ji-yi-hua-sou-suo-dong-tai-gui-hua-by-s/
• https://leetcode-cn.com/problems/coin-change/solution/322-ling-qian-dui-huan-by-leetcode-solution/

分析：这道题本质上其实跟70.爬楼梯是一样的，兑换金额 amount 得到的硬币数取决于兑换金额 amount-coins[i] 得到的硬币数，这里 coins[i] 指的是选取的第一个硬币是哪个。

解法一：递归+记忆化

递推公式：minCoinCount(coins, amount) = min(minCoinCount(amount-coins[0]), minCoinCount(amount-coins[1]), ...) + 1
终止条件：amount <= 0

class Solution {
    var memo: [Int] = [Int]()
    func coinChange(_ coins: [Int], _ amount: Int) -> Int {
        memo = [Int](repeating: Int.max, count: amount)
        return minCoinCountForChange(coins, amount)
    }

    // [2], 3
    private func minCoinCountForChange(_ coins: [Int], _ amount: Int) -> Int {
        guard amount > 0 else {
            return amount == 0 ? 0 : -1
        }

        // 取出缓存的结果
        if memo[amount-1] != Int.max {
            return memo[amount-1]
        }

        var cointCount = Int.max
        for coin in coins {
            var cointCountPrev = minCoinCountForChange(coins, amount-coin)
            if cointCountPrev != -1 { // 说明可以兑换
                cointCount = min(cointCount, cointCountPrev+1)
            }
        }
        // 缓存结果
        memo[amount-1] = cointCount == Int.max ? -1 : cointCount
        return memo[amount-1]
    }
}

时间复杂度：O(M*N)，其中 M 为 amount 的大小，N 为 coins 的大小
空间复杂度：O(M)，其中 M 为 amount 的大小

解法二：动态规划

状态定义：dp[amount]，兑换金额为 amount 所需的最少硬币数
状态转移方程：dp[amount] = 1 + min(dp[amount-coins[0]], dp[amount-coins[1]], ..., dp[amount-coins.last])
初始状态：dp[0] = 0
返回结果：dp[amount]
空间优化：

class Solution {

    func coinChange(_ coins: [Int], _ amount: Int) -> Int {
        guard amount > 0 else {
            return 0
        }
        var dp: [Int] = [Int](repeating: Int.max, count: amount+1)
        dp[0] = 0

        for tempAmount in 1...amount {
            for i in 0..<coins.count {
                let coinValue = coins[i]
                if coinValue <= tempAmount && dp[tempAmount-coinValue] != Int.max { // 可以兑换
                    dp[tempAmount] = min(1+dp[tempAmount-coinValue], dp[tempAmount]) 
                }
            }
        }
        return dp[amount] == Int.max ? -1 : dp[amount]
    }
}

时间复杂度：O(M*N)，其中 M 为 amount 的大小，N 为 coins 的大小
空间复杂度：O(M)，其中 M 为 amount 的大小

[ShannonChenCHN]

64. 最小路径和

2021.04.11 07:00 pm ~ 08:00 pm

示例：

输入：
grid = [
	[1,  3,  1],
	[1,  5,  1],
	[4,  2,  1]
]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

解法一：递归+记忆化

解法二：动态规划

状态定义：dp[i][j] 表示从左上角grid[0][0] 到网格 grid[i][j] 的最小路径和。
状态转移方程：
if (i > 0 && j > 0) dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
if (i == 0) dp[i][j] = grid[i][j] + dp[i][j-1])
if (j == 0) dp[i][j] = grid[i][j] + dp[i-1][j]
初始状态：dp[0][0] = grid[0][0]
返回结果：dp[m-1][n-1]

时间复杂度：O(m*n)
空间复杂度：O(m*n)

class Solution {
    func minPathSum(_ grid: [[Int]]) -> Int {
        let m = grid.count
        let n = grid.last!.count
        var dp: [[Int]] = [[Int]](repeating: [Int](repeating: 0, count: n), count: m)

        for i in 0..<m {
            for j in 0..<n {
                if i == 0 && j == 0 {
                    dp[i][j] = grid[i][j]
                } else if i == 0 {
                    dp[i][j] = grid[i][j] + dp[i][j-1]
                } else if j == 0 {
                    dp[i][j] = grid[i][j] + dp[i-1][j]
                } else {
                    dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
                }
            }
        }

        return dp[m-1][n-1]
    }
}

空间优化：空间优化有两种方法，一种是直接将 dp 结果覆盖 grid 中的数据，另一种是用一维数组维护每一行的 dp 结果即可。这里我们采用第二种方法。优化后的空间复杂度为 O(n)。

class Solution {
    func minPathSum(_ grid: [[Int]]) -> Int {
        let m = grid.count
        let n = grid.last!.count
        var dp: [Int] = [Int](repeating: 0, count: n)

        for i in 0..<m {
            for j in 0..<n {
                if i == 0 && j == 0 {
                    dp[j] = grid[i][j]
                } else if i == 0 {
                    dp[j] = grid[i][j] + dp[j-1] 
                } else if j == 0 {
                    dp[j] = grid[i][j] + dp[j]  // 换行
                } else {
                    dp[j] = grid[i][j] + min(dp[j], dp[j-1])  // 从当前行的第 j-1 个和上一行的第 j 个中取出最小的
                }
            }
        }

        return dp[n-1]
    }
}

[ShannonChenCHN]

72. 编辑距离（难度困难）

2021.04.11 08:00 pm ~ 08:30 pm
2021.04.12 08:00 am ~ 09:00 am, 12:00 pm ~12:23 pm

示例：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

参考题解：

• https://time.geekbang.org/course/detail/100019701-69785
• https://leetcode-cn.com/problems/edit-distance/solution/bian-ji-ju-chi-by-leetcode-solution/

分析

什么是编辑距离？编辑距离算法被数据科学家广泛应用，是用作机器翻译和语音识别评价标准的基本算法。

题目要求是：将 word1 转换成 word2 所使用的最少操作数，你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

解法一：递归+记忆化

https://leetcode.com/problems/edit-distance/discuss/1119440/Swift-20-ms-DP-solution

解法二：动态规划

状态定义：
dp[i][j] 表示 word1 前 i 个字母转换成 word2 前 j 个字母的最少操作数
（注意：这里是前 i 个和前 j 个）

动态转移方程：
dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]) if (word1[i-1] == word2[j-1])
dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+1) if (word1[i-1] != word2[j-1])
dp[i][j] = j if (i == 0)
dp[i][j] = i if (j == 0)

dp[i-1][j]+1 表示在 word2 的第 j-1 个位置添加了 1 个字母（其实也就相当于删除了 word1 的第 i-2 个字母）
dp[i][j-1]+1 表示在 word1 的第 i-1 个位置添加了 1 个字母（其实也就相当于删除了 word2 的第 j-2 个字母）
dp[i-1][j-1]+1 表示替换了 word1 的第 i-2 个字母（其实也就相当于替换了 word2 的第 j-2 个字母）
dp[i-1][j-1] 表示 word1 的第 i-1 个字母与 word2 的第 j-1 个字母相同

状态初始化：dp[0][0] = 0
返回结果：dp[m][n]

时间复杂度：O(m*n)
空间复杂度：O(m*n)

class Solution {
    func minDistance(_ word1: String, _ word2: String) -> Int {
        let m = word1.count
        let n = word2.count
        guard m > 0 && n > 0 else {
            return (m + n)
        }
        
        let s1 = Array(word1)
        let s2 = Array(word2)
        var dp: [[Int]] = [[Int]](repeating: [Int](repeating: 0, count: n+1), count: m+1)
        for i in 0...m {
            for j in 0...n {
                if i == 0 && j == 0 {
                    dp[i][j] = 0
                } else if i == 0 {
                    dp[i][j] = j
                } else if j == 0 {
                    dp[i][j] = i
                } else {
                    if s1[i-1] == s2[j-1] {
                        dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]) 
                    } else {
                        dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
                    }
                }
            }
        }

        return dp[m][n]
    }
}

空间优化：画出二维矩阵，发现我们每次循环其实只用到了一行，所以用一维数组就够了。
时间复杂度：O(m*n)
空间复杂度：O(n)

class Solution {
    func minDistance(_ word1: String, _ word2: String) -> Int {
        let m = word1.count
        let n = word2.count
        guard m > 0 && n > 0 else {
            return (m + n)
        }
        
        let s1 = Array(word1)
        let s2 = Array(word2)
        var dp: [Int] = [Int](repeating: Int.max, count: n+1)
        var dpLeftTop: Int = Int.max
        for i in 0...m {
            for j in 0...n {
                if i == 0 && j == 0 {
                    dp[j] = 0
                    dpLeftTop = 0
                } else if i == 0 {
                    dp[j] = j
                } else if j == 0 { // 换行
                    dpLeftTop = dp[j]
                    dp[j] = i
                } else {
                    let dpTop = dp[j]
                    let dpLeft = dp[j-1]
                    if s1[i-1] == s2[j-1] {
                        dp[j] = min(dpTop+1, dpLeft+1, dpLeftTop)
                    } else {
                        dp[j] = 1 + min(dpTop, dpLeft, dpLeftTop)
                    }
                    dpLeftTop = dpTop
                }
            }
        }

        return dp[n]
    }
}