动态规划2——初探

一、坐标型动态规划

例1. Unique Paths II

题目描述：
给定m行n列的网格，有一个机器人从左上角(0,0)出发，每一步可以向下或者向右走一步。网格中有些地方有障碍，机器人不能通过障碍格。问有多少种不同的方式走到右下角？（输入二维数组，如果数组的元素为1，表示该位置有障碍；为0表示没有障碍。）

解析：这题和Unique Path非常类似，只是网格中可能有障碍。最后一步一定是从左边(i, j-1)或上边(i-1, j)过来。状态f[i][j]表示从左上角有多少种方式走到格子(i, j) 。坐标型动态规划：数组下标 [i][j] 即坐标(i, j)，f[i][j] = f[i-1][j] + f[i][j-1]。

f[i][j] = 机器人有多少种方式从左上角走到(i, j)：

如果左上角(0, 0)格或者右下角(m-1, n-1)格有障碍，直接输出0
如果(i, j)格有障碍，f[i][j] = 0，表示机器人不能到达此格（0种方式）
初始条件：f[0][0] = 1
一般情况下：
如果(i, j)格有障碍，f[i][j] = 0
如果j=1，即第一列，f[i][j] = f[i-1][j]
如果i=1，即第一行，f[i][j] = f[i][j-1]
其他，f[i][j] = f[i-1][j] + f[i][j-1]

代码如下：

def uniquePathsWithObstacles(obstacleGrid):
    states = obstacleGrid
    for i in range(len(states)):
        for j in range(len(states[i])):
            if i == 0 and j == 0:
                states[i][j] = 1 - states[i][j]
            elif i == 0:
                if states[i][j] == 1:
                    states[i][j] = 0
                else:
                    states[i][j] = states[i][j - 1]
            elif j == 0:
                if states[i][j] == 1:
                    states[i][j] = 0
                else:
                    states[i][j] = states[i - 1][j]
            else:
                if states[i][j] == 1:
                    states[i][j] = 0
                else:
                    states[i][j] = states[i - 1][j] + states[i][j - 1]
    if states[-1][-1] > 2147483647:
        return -1
    else:
        return states[-1][-1]

例2. Longest Increasing Continuous Subsequence

题目描述：
给定a[0], …, a[n-1]，找到最长连续递增子序列i, i+1, i+2, …, j, 使得a[i]<a[i+1]<…<a[j]，输出长度j-i+1。
例子：
输入：[5, 1, 2, 3, 4]
输出：4 (子序列1, 2, 3, 4)

设f[j] =以a[j]结尾的最长连续上升子序列的长度，f[j] = max{ 1, f[j–1]+1| j>0 and a[j-1] < a[j]}。情况1：子序列就是a[j]本身；情况2：以a[j-1]结尾的最长连续上升子序列的长度，加上a[j]。

计算f[0], f[1], f[2], …, f[n-1]
• 和硬币组合题不一样的是，最终答案并不一定是f[n-1]
• 因为我们不知道最优策略中最后一个元素是哪个a[j]
• 所以答案是max{f[0], f[1], f[2], …, f[n-1]}
• 算法时间复杂度O(n)，空间复杂度O(n)

 def findLengthOfLCIS(nums):
        if len(nums) < 1:
            return 0
        states = [1]
        for i in range(1, len(nums)):
            if nums[i] > nums[i-1]:
                states.append(states[i-1] + 1)
            else:
                states.append(1)
        return max(states)

例3. Minimum Path Sum

题目描述：
给定m行n列的网格，每个格子(i, j)里都一个非负数A[i][j]。求一个从左上角(0, 0)到右下角的路径，每一步只能向下或者向右走一步，使得路径上的格子里的数字之和最小，输出最小数字和。

设从(0, 0)走到(i, j)的路径最小数字总和f[i][j]，f[i][j] = min{f[i-1][j], f[i][j-1]} + A[i][j] ，初始条件：f[0][0] = A[0][0]；边界情况：i = 0 或 j = 0，则前一步只能有一个方向过来。

• 计算第0行：f[0][0], f[0][1], …, f[0][n-1]
• 计算第1行：f[1][0], f[1][1], …, f[1][n-1]
• …
• 计算第m-1行：f[m-1][0], f[m-1][1], …, f[m-1][n-1]
• 时间复杂度（计算步数）：O(MN)，空间复杂度（数组大小）：O(MN)

def minPathSum(grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        for i in range(m):
            for j in range(n):
                if not i and not j:
                    continue
                if not i:
                    grid[i][j] += grid[i][j-1]
                elif not j:
                    grid[i][j] += grid[i-1][j]
                else:
                    grid[i][j] += min(grid[i][j-1], grid[i-1][j])
        return grid[m-1][n-1]

这种方式是在原数组上直接修改，考虑到计算第 i 行时，只需要第 i 行和第 i-1 行的 f，所以，只需要保存两行的f值：f[i][0..n-1]和f[i-1][0..n-1]，用滚动数组实现。实际操作时用滚动法：
• 计算f[0][0],..,f[0][n-1], 计算f[1][0],..,f[1][n-1]
• 计算f[2][0..n-1]时，把值写在f[0][0..n-1]的数组里
• 同理，f[3][0..n-1]写在f[1][0..n-1]的数组里
• 最后f[m-1][n-1]存储在f[0][n-1]（或者f[1][n-1]）里，直接输出。

滚动数组代码如下：

def minPathSum(grid: List[List[int]]) -> int:
        m = len(grid)  
        n = len(grid[0])
        states = [[0]*n]*2       
        for i in range(m):
            for j in range(n):
                if not i and not j:
                    states[i][j] = grid[i][j]
                elif not i:
                    states[i%2][j] = states[i%2][j-1] + grid[i][j]
                elif not j:
                    states[i%2][j] = states[(i+1)%2][j] + grid[i][j]
                else:
                    states[i%2][j] = min(states[i%2][j-1], states[(i+1)%2][j]) + grid[i][j]
        return states[(m-1)%2][n-1]

例4.Counting Bits

题目描述：
给定N，要求输出0, 1, …, N的每个数的二进制表示里的1的个数
例子：
输入：5
输出：[0, 1, 1, 2, 1, 2]
0：0
1：1
2：10
3：11
4：100
5：101

最后一步：观察这个数最后一个二进制位（最低位），去掉它，看剩下多少个1
(170)10 = (10101010) 2
(85)10 = (1010101) 2
85的二进制表示里有4个1
170的二进制表示里有4个1

设f[i]表示i的二进制表示中有多少个1，f[i] = f[i>>1] + (i & 1)。初始条件：f[0] = 0，依次计算 f[0], f[1], f[2], …, f[N]
• 时间复杂度O(N)
• 空间复杂度O(N)

def countBits(num: int) -> List[int]:
        states = [0] * (num+1)
        states[0] = 0
        for i in range(1, num+1):
            states[i] = states[i >> 1] + (i&1)
        return states

小结

坐标型动态规划是最简单的动态规划类型。
给定一个序列或网格，需要找到序列中某个/些子序列或网格中的某条路径（某种性质最大/最小、计数、存在性）。
动态规划方程 f[i] 中的下标 i 表示以 ai 为结尾的满足条件的子序列的性质，f[i][j] 中的下标i, j表示以格子(i, j)为结尾的满足条件的路径的性质（最大值/最小值、个数、是否存在）。
坐标型动态规划的初始条件f[0]就是指以a0为结尾的子序列的性质
二维空间优化：如果f[i][j]的值只依赖于当前行和前一行，则可以用滚动数组节省空间

二、序列型动态规划

给出一个序列：

动态规划方程f[i]中的下标i表示前i个元素a[0], a[1], ..., a[i-1]的某种性质（坐标型的f[i]表示以a i 为结尾的某种性质）
初始化中,f[0]表示空序列的性质（坐标型动态规划的初始条件f[0]就是指以a 0 为结尾的子序列的性质）

2.1 序列+状态型动态规划

例1. Paint House

题目描述：
有一排N栋房子，每栋房子要漆成3种颜色中的一种：红、蓝、绿，任何两栋相邻的房子不能漆成同样的颜色。第 i 栋房子染成红色、蓝色、绿色的花费分别是cost[i][0], cost[i][1], cost[i][2]。问最少需要花多少钱油漆这些房子？
例子：
输入： N=3 ; Cost = [[14,2,11],[11,14,5],[14,3,10]]
输出：10 （第0栋房子蓝色，第1栋房子绿色，第2栋房子蓝色, 2+5+3=10）

第一步：确定状态

最优策略是花费最小的策略。

最后一步
最优策略中最后一栋房子N一定染成了红、蓝、绿中的一种。但是相邻两栋房子不能漆成一种颜色：如果最优策略中房子N是红色，房子N-1只能是蓝色或绿色；如果最优策略中房子N是蓝色，房子N-1只能是红色或绿色；如果最优策略中房子N是绿色，房子N-1只能是红色或蓝色。如果直接套用以前的思路，记录油漆N栋房子的最小花费，根据套路，也需要记录油漆前N-1栋房子的最小花费。但是，前N-1栋房子的最小花费的最优策略中，又不知道第N-1栋房子是什么颜色，所以有可能和最后一栋房子N撞色。既然不知道房子N-1是什么颜色，就把它记录下来——分别记录油漆前N-1栋房子并且房子N-1是红色、蓝色、绿色的最小花费。
子问题
求油漆前N栋房子并且最后一栋房子N是红色、蓝色、绿色的最小花费，需要知道油漆前N-1栋房子并且房子N-1是红色、蓝色、绿色的最小花费。
状态：设油漆前i栋房子并且第 i 栋房子是红色、蓝色、绿色的最小花费分别为 f[i][0], f[i][1], f[i][2]

第二步：转移方程

设油漆前 i 栋房子并且第 i 栋房子是红色、蓝色、绿色的最小花费分别为 f[i][0], f[i][1], f[i][2] ，那么：

f[i][0] = min{f[i-1][1] + cost[i-1][0], f[i-1][2] + cost[i-1][0]}
f[i][1] = min{f[i-1][0] + cost[i-1][1], f[i-1][2] + cost[i-1][1]}
f[i][2] = min{f[i-1][0] + cost[i-1][2], f[i-1][1] + cost[i-1][2]}

（注意两个 i-1 的含义是不同的，我们的 i 指的是油漆 i 栋房子，f(i-1)指的是油漆 i-1 栋房子，而cost[i-1][0]指的是油漆第 i 栋房子为红色的花费，因为在数组里是从0开始计数的，油漆房子是从1开始计数的。）

第三步：初始条件和边界情况

初始条件：f[0][0] = f[0][1] = f[0][2] = 0 即不油漆任何房子的花费。
无边界情况

第四步：计算顺序

设油漆前i栋房子并且房子 i 是红色、蓝色、绿色的最小花费分别为f[i][0], f[i][1], f[i][2]
• 初始化f[0][0], f[0][1], f[0][2]
• 计算f[1][0], f[1][1], f[1][2]
…
• 计算f[N][0], f[N][1], f[N][2]
• 答案是min{f[N][0], f[N][1], f[N][2]}。时间复杂度O(N), 空间复杂度O(N)

代码如下：

def paint_house(n, costs):
    states = [[0, 0, 0]] + costs  # 在原数组改动，降低空间复杂度
    for i in range(1, n+1):
        states[i][0] += min(states[i-1][1], states[i-1][2])
        states[i][1] += min(states[i-1][0], states[i-1][2])
        states[i][2] += min(states[i-1][0], states[i-1][1])
    return min(states[n])

例2. Paint House II

题目描述：
有一排N栋房子，每栋房子要漆成 k 种颜色中的一种，任何两栋相邻的房子不能漆成同样的颜色。第 i 栋房子染成第 j 种颜色的花费是cost[i][j]。问最少需要花多少钱油漆这些房子？
例子：
输入： N=3, k=3 ; Cost = [[14,2,11],[11,14,5],[14,3,10]]
输出：10 （第0栋房子蓝色，第1栋房子绿色，第2栋房子蓝色, 2+5+3=10）

分析：
这题和Paint House非常类似,只是颜色种类变成K种，动态规划思路和Paint House一样,需要记录油漆前 i 栋房子并且房子第 i 栋房子是颜色1, 颜色2, ..., 颜色K的最小花费:f[i][1], f[i][2], ..., f[i][K]。设油漆前i栋房子并且房子 i 是颜色1, 颜色2, ...颜色K的最小花费分别为 f[i][1], f[i][2], ..., f[i][K]：
f[i][1] = min{f[i-1][2] + cost[i-1][1], f[i-1][3] + cost[i-1][1], ..., f[i-1][K] + cost[i-1][1]}
f[i][2] = min{f[i-1][1] + cost[i-1][2], f[i-1][3] + cost[i-1][2], ..., f[i-1][K] + cost[i-1][2]}
...
f[i][K] = min{f[i-1][1] + cost[i-1][K], f[i-1][2] + cost[i-1][K], ..., f[i-1][K-1] + cost[i-1][K]}

总之： $f[i][j] = min_{k ≠j} {f[i-1][k]} + cost[i-1][j]$

但是，设油漆前i栋房子并且房子i-1是颜色1, 颜色2, ...颜色K的最小花费分别为f[i][1], f[i][2], ..., f[i][K]
• f[i][j] = min k ≠j {f[i-1][k]} + cost[i-1][j]
• 直接计算的时间复杂度(计算步数):
– i从0到N
– j从1到K
– k从1到K
– O(NK 2 )
速度太慢了！

考虑到如果最小值是第 i 个元素,次小值是第 j 个元素：

只要除掉的元素不是第i个,剩下的最小值就是第 i 个元素
如果除掉的元素是第i个,剩下的最小值就是第 j 个元素

所以：
• 记录下f[i-1][1], ..., f[i-1][K]中的最小值和次小值分别是哪个
• 假如最小值是f[i-1][a], 次小值是f[i-1][b]
• 则对于j=1,2,3,...,a-1, a+1,...,K, f[i][j] = f[i-1][a] + cost[i-1][j]
• f[i][a] = f[i-1][b] + cost[i-1][a]
• 时间复杂度降为O(NK)

代码如下：

def paint_house2(n, k, costs):
    states = [[0]*k] + costs
    for i in range(1, n+1):
        cp = states[i-1].copy()
        cp.sort()
        min_num = cp[0]
        next_num = cp[1]
        idx = states[i-1].index(min_num)
        for j in range(k):
            if j != idx:
                states[i][j] += min_num
            else:
                states[i][j] += next_num
    return min(states[n])

例3. House Robber

题目描述：
有一排N栋房子(0~N-1),房子i里有A[i]个金币。一个窃贼想选择一些房子偷金币，但是不能偷任何挨着的两家邻居,否则会被警察逮住。最多偷多少金币？
• 例子:
• 输入:A={3, 8, 4}
• 输出:8 (只偷第二家的金币)

分析：
• 最后一步:窃贼的最优策略中,有可能偷或者不偷最后一栋房子N
• 情况1:不偷房子N
– 简单,最优策略就是前N-1栋房子的最优策略
• 情况2:偷房子N
– 仍然需要知道在前N-1栋房子中最多能偷多少金币,但是,需要保证不偷第N-2栋房子

用f[i][0]表示不偷房子 i 的前提下,前 i 栋房子中最多能偷多少金币；
用f[i][1]表示偷房子 i 的前提下,前 i 栋房子中最多能偷多少金币。
f[i][0] = max{f[i-1][0], f[i-1][1]}，因为不偷房子i-1,所以房子i-2可以选择偷或不偷；
f[i][1] = f[i-1][0] + A[i-1]，偷房子i-1,房子i-2必须不偷。

在不偷房子i-1的前提下,前i栋房子中最多能偷多少金币等价于前i-1栋房子最多能偷多少金币，所以我们可以简化前面的表示：
• 设f[i]为窃贼在前i栋房子最多偷多少金币
• f[i] = max{f[i-1], f[i-2] + A[i-1]}
• 初始条件:
– f[0] = 0 (没有房子,偷0枚金币)
– f[1] = A[0]
– f[2] = max{A[0], A[1]}

时间复杂度O(N), 空间复杂度O(1)

代码如下：

 def rob(nums: List[int]) -> int:
        n = len(nums)
        if n < 1:
            return 0
        if n == 1:
            return nums[0]
        dp = [0] * (n+1)
        dp[0] = 0
        dp[1] = nums[0]
        for i in range(2, n+1):
            dp[i] = max(dp[i-1], dp[i-2]+nums[i-1])
        return dp[n]

例4. House Robber II

题目描述：
有一圈N栋房子,房子i-1里有A[i]个金币，一个窃贼想选择一些房子偷金币，但是不能偷任何挨着的两家邻居,否则会被警察逮住。最多偷多少金币？
• 例子:
• 输入:A={3, 8, 4}
• 输出:8 (只偷房子1的金币)

分析：
这题和House Robber非常类似,只是房子现在排成一个圈，于是房子0和房子N-1成了邻居,不能同时偷盗：要么没偷房子0，要么没偷房子N-1。我们可以枚举窃贼是没有偷房子0还是没有偷房子N-1：
情况1:没偷房子0。最优策略就是窃贼对于房子1~N-1的最优策略->化为House Robber;
情况2:没偷房子N-1。最优策略就是窃贼对于房子0~N-2的最优策略->化为House Robber。

代码如下：

def houseRobber2(self, nums):
        n = len(nums)
        if n == 0:
            return 0
        if n == 1:
            return nums[0]
        dp = [0] * n
        dp[0], dp[1] = 0, nums[1]
        for i in range(2, n):
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
        answer = dp[n - 1]
        dp[0], dp[1] = nums[0], max(nums[0], nums[1])
        for i in range(2, n - 1):
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
        return max(dp[n - 2], answer)

例5. Best Time to Buy and Sell Stock

题目描述：
已知后面N天一支股票的每天的价格P 0 , P 1 , ..., P N-1，可以最多买一股卖一股。求最大利润。
• 例子:
• 输入:[3, 2, 3, 1, 2]
• 输出:1 (2买入,3卖出)

分析：
从0到N-1枚举j,即第几天卖，时刻保存当前为止(即0~j-1天)的最低价格P i，最大的P j - P i 即为答案。（千万别太僵硬！）

代码如下：

def maxProfit(prices: List[int]) -> int:
        if len(prices) < 1:
            return 0
        profit = 0
        low = prices[0]
        for price in prices:
            profit = max(profit, price-low)
            low = min(price, low)
        return profit

例6. Best Time to Buy and Sell Stock II

题目描述：
已知后面N天一支股票的每天的价格P 0 , P 1 , ..., P N-1，可以买卖一股任意多次,但任意时刻手中最多持有一股。求最大利润。
• 例子:
• 输入:[2, 1, 2, 0, 1]
• 输出:2 (1买入,2卖出,0买入,1卖出)

分析：
最优策略是如果今天的价格比明天的价格低,就今天买,明天卖(贪心)。正确性证明可以从这里下手:
如果最优策略第10天买,第15天卖,我们可以把它分解成5天,结果不会变差。

代码如下：

def maxProfit2(prices: List[int]) -> int:
        n = len(prices)
        if n < 2:
            return 0
        profit = 0
        for i in range(n-1):
            if prices[i] < prices[i+1]:
                profit += prices[i+1] - prices[i]
        return profit

小结

当思考动态规划最后一步时, 这一步的选择依赖于前一步的某种状态。
初始化时,f[0]代表前0个元素/前0天的情况（与坐标型动态规划区别）
计算时,f[i]代表前i个元素(即元素0~i-1)的某种性质

2.2 最长序列型动态规划

题目给定一个序列
• 要求找出符合条件的最长子序列
• 方法
– 记录以每个元素 i 结尾的最长子序列的长度
– 计算时,在 i 之前枚举子序列上一个元素是哪个

例1. Longest Increasing Subsequence

题目描述：
给定a[0], ..., a[n-1]，找到最长的子序列0<=i 1 <i 2 <...<i K <n, 使得a[i 1 ]<a[i 2 ]<...<a[i K ],输出K
例子:
输入:[4, 2, 4, 5, 3, 7]
输出:4 (子序列2, 4, 5, 7)

分析：
最后一步
对于最优的策略,一定有最后一个元素a[j]
• 第一种情况：最优策略中最长上升子序列就是{a[j]},答案是1
• 第二种情况：子序列长度大于1,那么最优策略中a[j]前一个元素是a[i], 并且a[i] < a[j]。
因为是最优策略,那么它选中的以a[i]结尾的上升子序列一定是最长的。

子问题
因为不确定最优策略中a[j]前一个元素a[i]是哪个,需要枚举每个i，求以a[i]结尾的最长上升子序列，本来是求以a[j]结尾的最长上升子序列，化为子问题: i < j。

状态
设f[j] =以a[j]结尾的最长上升子序列的长度。

转移方程
f[j] =以a[j]结尾的最长上升子序列的长度：
f[j] = max{ 1, f[i] + 1| i < j and a[i] < a[j]}
• 计算f[0], f[1], f[2], ..., f[n-1]
• 答案是max{f[0], f[1], f[2], ..., f[n-1]}
• 算法时间复杂度O(n² ),空间复杂度O(n)

代码如下：

def lengthOfLIS(nums: List[int]) -> int:
        n = len(nums)
        if n < 1:
            return 0
        dp = [1] * n
        dp[0] = 1
        for i in range(1, n):
            subs = [dp[j] for j in range(i) if nums[j] < nums[i]]
            if subs:
                dp[i] = max(subs) + 1
        return max(dp)

O(NlogN)的解法：

tails is an array storing the smallest tail of all increasing subsequences with length i+1 in tails[i].
For example, say we have nums = [4,5,6,3], then all the available increasing subsequences are:

len = 1 : [4], [5], [6], [3] => tails[0] = 3
len = 2 : [4, 5], [5, 6] => tails[1] = 5
len = 3 : [4, 5, 6] => tails[2] = 6

We can easily prove that tails is a increasing array. Therefore it is possible to do a binary search in tails array to find the one needs update.

Each time we only do one of the two:

(1) if x is larger than all tails, append it, increase the size by 1
(2) if tails[i-1] < x <= tails[i], update tails[i]

Doing so will maintain the tails invariant. The the final answer is just the size.

def lengthOfLIS(self, nums):
    tails = [0] * len(nums)
    size = 0
    for x in nums:
        i, j = 0, size
        while i != j:
            m = (i + j) / 2
            if tails[m] < x:
                i = m + 1
            else:
                j = m
        tails[i] = x
        size = max(i + 1, size)
    return size

例2. Russian Doll Envelopes

题目描述：
给定N个信封的长度和宽度，如果一个信封的长和宽都分别小于另一个信封的长和宽,则这个信封可
以放入另一个信封
• 问最多嵌套多少个信封
• 例子:
• 输入:[[5,4],[6,4],[6,7],[2,3]]
• 输出:3 ([2,3] => [5,4] => [6,7])

状态
设f[j] =以a[j]结尾的最长上升子序列的长度。

代码如下：

def lengthOfLIS(nums: List[int]) -> int:
        n = len(nums)
        if n < 1:
            return 0
        dp = [1] * n
        dp[0] = 1
        for i in range(1, n):
            subs = [dp[j] for j in range(i) if nums[j] < nums[i]]
            if subs:
                dp[i] = max(subs) + 1
        return max(dp)

三、划分型动态规划

给定长度为N的序列或字符串,要求划分成若干段：

段数不限，或指定K段
每一段满足一定的性质

做法类似于序列型动态规划，但是通常要加上段数信息。一般用f[i][j]记录前 i 个元素(元素0~i-1)分成j段的性质,如最小代价。

例1. Decode Ways

题目描述：
有一段由A-Z组成的字母串信息被加密成数字串，加密方式为：A->1, B->2, …, Z->26。给定加密后的数字串S[0…N-1]，问有多少种方式解密成字母串？
例子：
输入： 12
输出： 2 (AB 或者 L)

第一步：确定状态

解密数字串即划分成若干段数字，每段数字对应一个字母。

最后一步
最后一步或一段一定对应一个字母 A, B, …, 或Z，这个字母加密时变成1, 2, …, 或26。

子问题
设数字串长度为N，要求数字串前N个字符的解密方式数，需要知道数字串前N-1和N-2个字符的解密方式数。
状态：设数字串S前 i 个数字解密成字母串有 f[i] 种方式。

第二步：转移方程

设数字串S前 i 个数字解密成字母串有 f[i] 种方式：

f[i] = f[i-1] | S[i-1]对应一个字母 + f[i-2] | S[i-2]S[i-1]对应一个字母。

第三步：初始条件和边界情况

初始条件：f[0] = 1，即空串有1种方式解密，解密成空串
边界情况：如果i = 1, 只看最后一个数字，f[1] = 1

第四步：计算顺序

依次计算 f[0], f[1], …, f[N]
• 答案是f[N]
• 时间复杂度O(N), 空间复杂度O(N)

代码如下：

def numDecodings(s: str) -> int:
        if s == "" or s[0] == '0':
            return 0
        s = ' ' + s  # 为了把f(0) = 0 带入计算，将 s 延长 1
        dp = [1, 1]  # 初始化 f(0) 和 f(1)
        for i in range(2, len(s)):
            if 10 <= int(s[i-1 : i+1]) <=26 and s[i] != '0':
                dp.append(dp[i-1] + dp[i-2])
            elif s[i-1 : i+1] == '10' or s[i-1 : i+1] == '20':
                dp.append(dp[i-2])
            elif s[i] != '0':  # 零只能用来构成 10 或 20，否则无法解码
                dp.append(dp[i-1])
            else:
                return 0
        return dp[len(s)-1]

例2. Perfect Squares

题目描述：
给定一个正整数n，问最少可以将n分成几个完全平方数(1,4,9,...)之和？
例子：
输入： n=13
输出： 2 (13=4+9)

第一步：确定状态

最后一步
关注最优策略中最后一个完全平方数 j²，最优策略中n-j² 也一定被分成最少的完全平方数之和。
子问题
所以需要知道n-j² 最少被分成几个完全平方数之和。原来是求 n 最少被分成几个完全平方数之和。
状态：设 f[i] 表示 i 最少被分成几个完全平方数之和

第二步：转移方程

设f[i]表示i最少被分成几个完全平方数之和：
$f[i] = min_{1<=j*j<=i} (f[i-j^2 ] + 1)$

第三步：初始条件和边界情况

初始条件：0被分成0个完全平方数之和，f[0] = 0

第四步：计算顺序

依次计算 f[0], f[1], …, f[N]
• 答案是f[N]
• 时间复杂度O(N^1.5), 空间复杂度O(N^1.5)

代码如下：

def numSquares(n: int) -> int:
    dp = [0] * (n+1)
    dp[1] = 1
    for i in range(2, n+1):
        temp = [dp[i-j*j] for j in range(1, int(i**0.5)+1)]
        dp[i] = min(temp) + 1
    return dp[n]

例3. Palindrome Partitioning II

题目描述：
给定一个字符串S[0..N-1]，要求将这个字符串划分成若干段,每一段都是一个回文串(正反看起来一样)。求最少划分几次？
例子:
输入: “aab”
输出: 1 (划分1次 “aa”, “b”)

第一步：确定状态

最后一步
关注最优策略中最后一段回文串，设为S[j..N-1]
子问题
求S前N个字符S[0..N-1]最少划分为几个回文串，需要知道S前 j 个字符[0..j-1]最少可以划分成几个回文串，减小问题规模。
状态
设S前 i 个字符S[0..i-1]最少可以划分成 f[i] 个回文串。

第二步：转移方程

$f[i] = min_{j=0,...,i-1 并且 S[j..i-1]是回文串} (f[j] + 1)$

注意：f[i] 表示前 i 个字符可以划分成多少回文字符串，这里的 i 指字符串长度。f[i-1] 表示前 i-1 个字符可以分成多少个；而 S[j..i-1] 是下标，比如 j=i-1 时，f[i-1]如前所述，而S[i-1..i-1]指的是最后那个字符。

如何判断回文字符串？

可以用两个指针从两头向中间移动,每一步两个指针指向的字符都必须相等。但是每次都判断S[j..i-1]是不是回文串很慢，可以用 isPalin[i][j] 记录S[i..j]是否是回文串，这样在主程序内直接检查即可。转移方程变为：

$f[i] = min_{j=0,...,i-1\ \text{and} \ isPalin[j][i-1] = True} (f[j] + 1)$

第三步：初始条件和边界情况

初始条件：空串被分成0个回文串，f[0] = 0

第四步：计算顺序

依次计算 f[0], f[1], …, f[N]
• 答案是f[N]-1 ，因为f[i]是划分多少回文串，而问题是划分多少次。（f[0]除外）
• 时间复杂度O(N²), 空间复杂度O(N²)

代码如下：

def minCut(s: str) -> int:
    n = len(s)
    if n == 0:
        return 0
    # 记录回文字符串
    P = [[False]*n for _ in range(n)]
    for i in reversed(range(n)):
        for j in range(i, n):
            if (s[i] == s[j] and (j - i < 2 or P[i + 1][j - 1])):
                P[i][j] = True
    # 寻找最少划分
    dp = [0]*(n+1)
    dp[1] = 1
    for i in range(2, n+1):
        temp = [dp[j]+1 for j in range(i) if P[j][i-1]]
        dp[i] = min(temp)
    return dp[n]-1

最后编辑于：2019.05.14 11:37:23

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 203,547评论 6赞 477
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,399评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 150,428评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,599评论 1赞 274
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,612评论 5赞 365
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,577评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,941评论 3赞 395
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,603评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,852评论 1赞 297
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,605评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,693评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,375评论 4赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,955评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,936评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,172评论 1赞 259
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 43,970评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,414评论 2赞 342

动态规划2——初探

一、坐标型动态规划

例1. Unique Paths II

例2. Longest Increasing Continuous Subsequence

例3. Minimum Path Sum

例4.Counting Bits

小结

二、序列型动态规划

2.1 序列+状态型动态规划

例1. Paint House

第一步：确定状态

第二步：转移方程

第三步：初始条件和边界情况

第四步：计算顺序

例2. Paint House II

例3. House Robber

例4. House Robber II

例5. Best Time to Buy and Sell Stock

例6. Best Time to Buy and Sell Stock II

小结

2.2 最长序列型动态规划

例1. Longest Increasing Subsequence

例2. Russian Doll Envelopes

三、划分型动态规划

例1. Decode Ways

第一步：确定状态

第二步：转移方程

第三步：初始条件和边界情况

第四步：计算顺序

例2. Perfect Squares

第一步：确定状态

第二步：转移方程

第三步：初始条件和边界情况

第四步：计算顺序

例3. Palindrome Partitioning II

第一步：确定状态

第二步：转移方程

第三步：初始条件和边界情况

第四步：计算顺序

推荐阅读更多精彩内容