算法锦囊2：一文搞定动态规划

这是我参与更文挑战的第8天，活动详情查看： 更文挑战

最近想把自己刷算法题的经验心得整理一下，一方面为了复习巩固，另一方面也希望我的分享能够帮助到更多在学习算法的朋友。

专栏名称叫《算法锦囊》，在讲解算法时会注重整体的结构性，但不会面面俱到，适合有一定算法经验的人阅读。

第一篇讲动态规划，这一部分的所有题目和源码都上传到了github的该目录下，题解主要用Python语言实现。

概述

如果让我用一句话来描述动态规划题目的精髓，就是去找重复子问题。

其实分治递归回溯和动态规划都有很多共性，都是要找重复子问题，只是在具体的实现思路上有区别。等到算法做多了就会发现，哪道题该用什么方法都能灵活运用了，而且一道题往往可以用多种写法去做。

动态规划最难的是找DP方程，只要明白了DP方程怎么写，面对特定的一道题就游刃有余了。

所以动态规划题存在一种情况，有思路的人很快就会做出来，没思路的人很难做出来，所以这类题在算法面试中很难体现出候选人的真实水平，因此出镜率并不高。

实战模拟

接下来，我选择一些典型例题来讲解，这些题目基本囊括了动态规划的方方面面，可以从中窥探到动弹规划的全貌。

70. 爬楼梯

题目地址为：leetcode-cn.com/problems/cl…

这是非常经典的题目，可以用递归解答（注意记忆化），也可以用迭代法，即动态规划。

dp方程为：f(x)=f(x−1)+f(x−2)

class Solution:
    def climbStairs(self, n: int) -> int:
        a, b = 1, 1
        for _ in range(n):
            a, b = b, a+b
        return a
复制代码

53. 最大子序和

题目地址：leetcode-cn.com/problems/ma…

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

dp方程为：f(i)=max{f(i−1)+nums[i],nums[i]}

对于每个元素，它的最大子序和，要么跟前面累加，要么就是自己独立。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1, len(nums)):
            nums[i] = max(nums[i], nums[i]+nums[i-1])
        return max(nums)

复制代码

这道题是dp里面比较简单的类型，只要找出一条线性的递归关系即可

152. 乘积最大子数组

题目地址：leetcode-cn.com/problems/ma…

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

这道题的难点在于，一个dp方程满足不了，需要分正负性来讨论，因此利用两个dp解决问题。

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        mi = ma = res = nums[0]
        for i in range(1, len(nums)):
            if nums[i] < 0: mi, ma = ma, mi
            ma = max(ma * nums[i], nums[i])
            mi = min(mi * nums[i], nums[i])
            res = max(res, ma)
        return res
复制代码

198. 打家劫舍

题目地址：leetcode-cn.com/problems/ho…

这道题是面试中的高频考题，也是简单的线性规划。

我这里提供的解法没有用dp数组，可以省去线性存储空间。

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0

        size = len(nums)
        if size == 1:
            return nums[0]
        
        first, second = nums[0], max(nums[0], nums[1])
        for i in range(2, size):
            first, second = second, max(first + nums[i], second)
        
        return second
复制代码

打家劫舍的升级版：213. 打家劫舍 II，地址：leetcode-cn.com/problems/ho…

如果房屋为环形，则分别去掉首位，两次动态规划。

class Solution:
    def rob(self, nums: List[int]) -> int:
        def my_rob(nums):
            cur, pre = 0, 0
            for num in nums:
                cur, pre = max(pre + num, cur), cur
            return cur
        return max(my_rob(nums[:-1]),my_rob(nums[1:])) if len(nums) != 1 else nums[0]
复制代码

91. 解码方法

题目地址：leetcode-cn.com/problems/de…

这道题有一定难度，需要考虑的case非常多，也是非常经典的一道动态规划题。

class Solution:
    def numDecodings(self, s: str) -> int:
        dp = [0] * len(s)
        # 考虑第一个字母
        if s[0] == "0":
            return 0
        else:
            dp[0] = 1
        if len(s) == 1: return dp[-1]
        # 考虑第二个字母
        if s[1] != "0":
            dp[1] += 1
        if 10 <= int(s[:2]) <= 26:
            dp[1] += 1
        for i in range(2, len(s)):
            # 当出现连续两个0
            if s[i - 1] + s[i] == "00": return 0
            # 考虑单个字母
            if s[i] != "0":
                dp[i] += dp[i - 1]
                if 10 <= int(s[i - 1] + s[i]) <= 26:
                    dp[i] += dp[i - 2]
            # 考虑两个字母
            else:
                if 1 <= int(s[i-1]) <= 2:
                     dp[i] += dp[i - 2]
                else:
                    return 0
        return dp[-1]
复制代码

62. 不同路径

题目地址：leetcode-cn.com/problems/un…

前面基本讨论了一维的动态规划，其实dp方程也可以是二维，比如这道非常经典的不同路径系列题目。

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1] * m]
        for _ in range(n-1):
            dp.append([1] + [0] * (m-1))
        for i in range(1, m):
            for j in range(1, n):
                dp[j][i] = dp[j-1][i] + dp[j][i-1] 

        return dp[-1][-1]
复制代码

这道题还有很多变体。

63. 不同路径 II leetcode-cn.com/problems/un…

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        n = len(obstacleGrid)
        if not n: return 0
        m = len(obstacleGrid[0])
        if not m: return 0
        dp = [[0]*m for _ in range(n)]
        for i in range(0, m):
            if obstacleGrid[0][i] == 1: break
            dp[0][i] = 1
        for j in range(0, n):
            if obstacleGrid[j][0] == 1: break
            dp[j][0] = 1
        for i in range(1, n):
            for j in range(1, m):
                if obstacleGrid[i][j] == 1:
                    dp[i][j] = 0
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[-1][-1]
复制代码

980. 不同路径 III leetcode-cn.com/problems/un…

不同路径III用到了回溯的思路，后面会有专门的递归专题讲这类解法。

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        R, C = len(grid), len(grid[0])
        self.res = 0
        sr, sc = 0, 0                     #起点 终点
        er, ec = 0, 0
        step = 0                        #非障碍的个数
        for r in range(R):
            for c in range(C):
                if grid[r][c] == 1:     sr, sc = r, c
                if grid[r][c] == 2:     er, ec = r, c
                if grid[r][c] != -1:    step += 1

        def dfs_backtrace(r, c, step):
            step -= 1
            if r == er and c == ec:
                if step == 0:
                    self.res += 1
                return
            grid[r][c] = -1
            for nr,nc in ((r-1,c),(r,c+1),(r+1,c),(r,c-1)):
                if 0<=nr<R and 0<=nc<C and grid[nr][nc] != -1:
                    dfs_backtrace(nr, nc, step)
            grid[r][c] = 0              #回溯算法
            
        dfs_backtrace(sr, sc, step)
        return self.res

复制代码

72. 编辑距离

题目地址：leetcode-cn.com/problems/ed…

我们最后来看这道题，编辑距离。

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

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

示例：

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

这道题看似没思路，其实也是动态规划，而且要借助二维矩阵。

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        row, col = len(word1)+1, len(word2)+1
        dp = [[0] * col for _ in range(row)]
        for i in range(0, row):
            dp[i][0] = i
        for j in range(0, col):
            dp[0][j] = j
        for i in range(1, row):
            for j in range(1, col):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
        return dp[-1][-1]
复制代码