线性DP

打家劫舍

这几道题的本质是线性DP中用 f[i][k]f[i][k]来表示在房子 ii 是否rob的最大收益。

f[i][k]={not rob:f[i][0]=max⁡(f[i−1])rob:f[i][1]=f[i−1][0]+nums[i]f[i][k] = \begin{cases} \text{not rob:} f[i][0]=\max(f[i-1]) \\ \text{rob:} f[i][1] = f[i-1][0]+\text{nums}[i] \\ \end{cases}

因为 f[i]f[i] 只和 f[i−1]f[i-1] 有关，这样的二维DP可以压缩空间到一维，甚至压缩到两个变量来解决。

  1. 打家劫舍

  2. 打家劫舍 II：环形结构，分情况讨论就好。

  3. 打家劫舍 III：树上DP，从root开始DFS，每次返回两个变量

  4. 删除并获得点数：把点数放在数组上，转化成打家劫舍I

  5. 3n 块披萨：延伸，二维f[i][j]f[i][j]来表示在 ii 点已经rob了 jj 个屋子的最大收益。

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，
影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，
计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。
def rob(nums):
    pre = cur = 0
    for n in nums:
        pre, cur = cur, max(cur, pre+n)
    return cur

粉刷房子

这几道题的本质使用二维DP中f[i][k]f[i][k] 来表示把第 ii 个房子涂成 kk 色的最小花费。

  1. 粉刷房子： k=1,2,3.k=1, 2, 3.

  2. 粉刷房子 II

  3. 粉刷房子 III：用三维数组来表示把第 ii 个房子涂成 jj 色形成 kk 个街区的最小花费。

假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，
你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。

当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。
每个房子粉刷成不同颜色的花费是以一个 n x 3 的矩阵来表示的。

例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；
costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。
请你计算出粉刷完所有房子最少的花费成本。

输入: [[17,2,17],[16,16,5],[14,3,19]]
输出: 10
解释: 将 0 号房子粉刷成蓝色，1 号房子粉刷成绿色，2 号房子粉刷成蓝色。
     最少花费: 2 + 5 + 3 = 10。
def minCost(costs):
    n = len(costs)
    f = [[float('inf')]*3 for _ in range(n+1)]
    f[0] = [0, 0, 0]
    for i in range(1, n+1):
        for k in range(3):
            f[i][k] = min([costs[i-1][k] + f[i-1][l]
                           for l in range(3) if l!=k])
    return min(f[-1])

买卖股票

这几道的本质是用二维DP中f[i][k]f[i][k] 来表示在 ii 天执行kk动作后的最大收益。因为股票要买了以后才能卖，而且在延伸题中对交易次数的限制，或者冷冻期的限制，我们可能要拓展状态 kk 或者引入第三个维度 f[i][k][m]f[i][k][m] 来记录已经完成了 mm 个交易。

由于在转移方程中 f[i]f[i] 只与前一天 f[i−1]f[i-1]有关，我们可以用滚动数组来节约第一个时间维度。

  1. 买卖股票的最佳时机：总共只能买卖各一次

  2. 买卖股票的最佳时机 II：每天可以买或卖一次，必须在再次购买前出售，可以完成无限笔

  3. 买卖股票的最佳时机 III：同二，最多完成两笔交易

  4. 买卖股票的最佳时机 IV：同三，最多完成K笔交易

  5. 最佳买卖股票时机含冷冻期：同二，卖出之后锁定一天

  6. 买卖股票的最佳时机含手续费：同二，每次交易有手续费fee

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。
设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，
     最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
def maxProfit(prices):
    sell, buy = 0, float('-inf')
    for p in prices:
        buy = max(buy, -p)
        sell = max(sell, buy+p)
    return sell

# 压缩空间前：
def maxProfit(prices):
    f = [[0]*2 for _ in range(len(prices)+1)]
    f[0][1] = float('-inf')
    for i, p in enumerate(prices, 1):
        f[i][0] = max(f[i-1][0], f[i-1][1]+p)
        f[i][1] = max(f[i-1][1], -p)
    return f[-1][0]

# 另一种解法：转化成最大子串
def maxSubarray(nums):
    res = pre = 0
    for n in nums:
        pre = max(pre+n, n)
        res = max(res, pre)
    return res

def maxProfit(prices):
    diff = []
    pre = prices[0]
    for p in prices[1:]:
        diff.append(p-pre)
        pre = p
    return self.maxSubarray(diff)

字符串匹配

这里把单串线性动态规划留到专题：子串/子序列最值。

下面这几道题是经典的双串问题。本质是用 f[i,j]f[i, j] 来表示第一串考虑[0, ..i]，第二串考虑[0, ...j]的答案。转移方程一般为：

f[i,j]=g(f[i−1][j]+cost1,f[i][j−1]+cost2,f[i−1][j−1]+cost3).f[i, j] = g(f[i-1][j] + \text{cost}_1, f[i][j-1]+ \text{cost}_2, f[i-1][j-1]+ \text{cost}_3).

方程中一直增加的是 ii 和 jj ，所以迭代顺序ii 和 jj从小到大就好了。

  1. 最长公共子序列（LCS）：最长的公共subsequence

  2. 最长公共子数组（LCSubarray）：最长的公共subarray

  3. 两个字符串的最小ASCII删除和（ASCII）

  4. 编辑距离（Edit Distance）

  5. 通配符匹配（Wildcard Matching）

  6. 正则表达式匹配（Regex Matching）

  7. 不同的子序列（Distinct)

  8. 扰乱字符串（Scramble）：f[i,j,l]f[i, j, l] = 从 s1[i]s_1[i] 和 s2[j]s_2[j] 开始的长度为 ll 的子串是否match。match的可能有两种，所以枚举中点 ww 

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。
如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：
它是由原字符串在不改变字符的相对顺序的情况下删除某些字符
（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。
def longestCommonSubsequence(text1, text2):
    m, n = len(text1), len(text2)
    f = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if text1[i-1]==text2[j-1]:
                f[i][j] = f[i-1][j-1]+1
            else:
                f[i][j] = max(f[i][j-1], f[i-1][j])
    return f[-1][-1]

跳跃游戏

在每一个点的可能跳到的目的地有所限制，求可行解或者最优解（最少步数，最大分数等）。用动态规划或者图的搜索方法DFS/BFS求解。如果需要优化，基本上是用贪心来加速（I，II，VI）。

  1. 跳跃游戏：能否跳到最后点。

  2. 跳跃游戏 II：跳到最后点的最少步数

  3. 跳跃游戏 III：能否从start可以前后跳跃至end。DFS细节：

    1. 为什么要vis数组。因为可能有cycle。

    2. 为什么DFS不一定需要回溯，因为没有死胡同。事实上，终点就是死胡同：因为arr[终点]=0

  4. 跳跃游戏 IV：与III类似用BFS+vis标记

  5. 跳跃游戏 V： [i−D,i+D][i-D, i+D] 跳跃区间，从高处向下跳的最多步数。DP解法需要先把问题排序。

  6. 跳跃游戏 VI： [i+1,i+max⁡][i+1, i+\max] 跳跃区间，得分最高的路径。用大顶堆贪心优化可以减少时间。

  7. 跳跃游戏 VII： [i+min⁡,i+max⁡][i+\min, i+\max] 跳跃区间，能否跳到最后点。难点是用O(n)来更新能到达的地点，用far来标记能到达的最远距离

  8. 青蛙过河： [step−1,step,step+1][\text{step}-1, \text{step}, \text{step}+1] 跳跃区间，能否跳到最后点。

  9. 最少侧跳次数：递归DP

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
def canJump(nums):
    far = 0
    for i, step in enumerate(nums):
        if far < i: return False
        far = max(far, i+step)
    return True
Previous记忆化搜索Next区间DP

Last updated

Was this helpful?