动态规划问题

这类问题的求解思路是：

• 先尝试有 Cache 的暴力搜索，列出递推式
• 将上述搜索转化为使用 dp 数组的方法
• 尝试压缩 dp 数组维度

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

746. 使用最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。 输入：cost = [10,15,20] 输出：15 解释：你将从下标为 1 的台阶开始。

• 支付 15 ，向上爬两个台阶，到达楼梯顶部。 总花费为 15 。

设 $dp[i]$ 为走到位置 i 所需的最小 cost：

62. 不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。 问总共有多少条不同的路径？

设 $dp[i][j]$ 表示由 (0,0) 走到(i,j)的路径数目

343. 整数拆分

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。 返回 你可以获得的最大乘积 。

• $dp[i]$ 表示拆解i可得的最大乘积
• 递推时，数 a 可拆解为 b+c 的形式，而 b，c 可以进一步拆分（其最大乘积为 $dp[b]$ ），也可以不拆分

96. 不同的二叉搜索树

#mark/leetcode 未做出来

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

思路：

• 设 $dp_n$ 为以 n 个结点的二叉搜索树的数目
• 以 n=3 为例， $dp_3$ =以 1 为根的搜索树数目+以 2 为根的搜索树数目+以 3 为根的搜索树数目
• 以 2 为根的搜索树数目=左子树数目×右子树数目= $dp[2-1]*dp[3-2]$

198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

• 设 $f[i]$ 偷窃前 i+1 家获得的最高金额
• 递推式： $f[i]=max(f[i-2]+v[i],f[i-1])$
• 初始条件： $f[0]=v[0],f[1]=max(v[0],v[1])$

213. 打家劫舍 II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，今晚能够偷窃到的最高金额。

输入：nums = [2,3,2] 输出：3 解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

思路：将环形数组从某处断开，形成一个普通数组。忽略数组的最后一个元素，然后用 198 题同样的思路求解。 遍历所有可能的断开的点，计算最大值 优化：只需考虑从 tail→head 处和 tail-1→tail 处断开的两种情况即可

337. 打家劫舍 III (树形 DP)

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。 除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。 给定二叉树的 root 。返回在不触动警报的情况下，小偷能够盗取的最高金额。

树的特点决定了，尽量不要跨 2 层及以上访问子结点，否则有很多判断情况，效率不高

思路：本质和 198. 打家劫舍 思路一样，但是这个思路的递推式 $f[j]=max(nums[j]+f[j-2],f[j-1])$ 会跨 2 层访问结点。优化思路是，后根遍历，计算每个树结点存储偷/不偷所能获得的最大金额（2 个数），这样无需跨 2 层访问。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def rob(self, root: Optional[TreeNode]) -> int:
	def maxAmount(root) -> tuple[int, int]:  # 返回偷，不偷root可以获得的最大金额
	    if root == None:
	        return (0, 0)
	    else:
	        lchild = maxAmount(root.left)
	        rchild = maxAmount(root.right)
	        theftAmount = root.val + lchild[1] + rchild[1]
	        noTheftAmount = max(lchild) + max(rchild) # 可偷可不偷
	
	        return (theftAmount, noTheftAmount)

return max(maxAmount(root))

5. 最长回文子串 - 力扣（LeetCode）

给你一个字符串 s，找到 s 中最长的回文子串。

P(i,j) 表示$s[i:j]$是否为回文串。

• P(i,j)为回文串当且仅当 $s[i+1,j-1]$ 为回文串且 $s[i]=s[j]$
• 边界条件为：
  • 长度 1：$s[i,i]=true$
  • 长度 2：$s[i,i+1]=s[i]==s[j]$

买卖股票的最佳时机

限制交易数

6. 121. 买卖股票的最佳时机 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
7. 122. 买卖股票的最佳时机 II ：可以先购买，然后在 同一天 出售。
8. 123. 买卖股票的最佳时机 III ：最多可以完成 两笔 交易。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
9. 188. 买卖股票的最佳时机 IV ：最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。

第 1,2 问可以用贪心做：遍历 prices，记录最低价格，利润=当前价格-最低价格，记录最大利润即可

第 3,4 问只能用动规：状态：不持有股票→持有股票（第 1 次）→不持有股票（第 1 次）→…→持有股票（第 k 次）→不持有股票（第 k 次） $dp[i,j]$ ：表示第 i 天处于状态 j 可以获得的最大总利润

• 每天有以下 3 种可能的操作

例如允许买入卖出 2 次时，计算最大例如的程序如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def maxProfit(self, prices: List[int]) -> int:
	day_cnt, state_cnt = len(prices), 4
	dp = [[0 for _ in range(state_cnt)] for _ in range(day_cnt + 1)]
	dp[0][0] = -prices[0]
	dp[0][2] = dp[0][0]
	for i in range(1, day_cnt + 1):
	    p = prices[i - 1]
	    dp[i][0] = max(dp[i - 1][0], -p)  # 买
	    dp[i][1] = max(dp[i - 1][1], dp[i][0] + p)  # 卖
	    dp[i][2] = max(dp[i - 1][2], dp[i][1] - p)  # 买
	    dp[i][3] = max(dp[i - 1][3], dp[i][2] + p)  # 卖
	    print(f"第{i}天,价格{p},总利润：{dp[i]}")
	return dp[day_cnt][state_cnt - 1]

限制交易间隔

309. 买卖股票的最佳时机含冷冻期 给定一个整数数组prices，其中第  prices[i] 表示第 i 天的股票价格 。​ 设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

• 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

设第 i 天处于买入状态可以获得的最大利润为 $buy[i]$ ，处于卖出状态可以获得的最大总利润为 $sell[i]$ ,处于冻结状态可以获得的最大总利润为 $frozen[i]$

含手续费

714. 买卖股票的最佳时机含手续费 给定一个整数数组 prices，其中 $prices[i]$ 表示第 i 天的股票价格；整数 fee 代表了交易股票的手续费用。返回获得利润的最大值。 你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。 注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

思路：buy 的时候计算手续费即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def maxProfit(self, prices: List[int], fee: int) -> int:
	n = len(prices) + 1
	buy = [-50000] * n
	sell = [0] * n
	for i in range(1, n):
	    p = prices[i - 1]
	    buy[i] = max(buy[i - 1], sell[i - 1] - p - fee)
	    sell[i] = max(sell[i - 1], buy[i] + p)
	
	return sell[-1]

子序列问题

300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 设 $dp[i]$ 为以 $nums[i]$ 为最后一个元素的增序列长度：

1
2
3
4
5

def findLengthOfLCIS(self, nums: List[int]) -> int:
	dp = [1] * len(nums)
	for i in range(1, len(nums)):
	    dp[i] = dp[i - 1] + 1 if nums[i] > nums[i - 1] else 1
	return max(dp)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

int maxValue_ver1(int backpackSize, vector<int> itemWeight,
                  vector<int> itemValue) {
  // dp[i][j]的含义：从下标为[0-i]的物品⾥任意取，放进容量为j的背包，价值总和最⼤是多少
  vector<int> dp(backpackSize + 1, 0);
  for (int i = 0; i < itemValue.size(); ++i) {             // 遍历物品
    for (int j = backpackSize; j >= itemWeight[i]; --j) {  // 遍历背包容量
      dp[i] = max(dp[j], dp[j - itemWeight[i]] + itemValue[i]);
    }
  }
  return dp[backpackSize];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
    cnts = []
    for s in strs:
        rn0 = s.count("0")
        cnts.append((rn0, len(s) - rn0))

    # 初始化DP数组
    dp = [[0 for _ in range(1 + n)] for _ in range(1 + m)]

    for i in range(len(strs)):
        rn0, rn1 = cnts[i]
        for n0 in range(m, rn0 - 1, -1):
            for n1 in range(n, rn1 - 1, -1):
                dp[n0][n1] = max(dp[n0][n1], dp[n0 - rn0][n1 - rn1] + 1)

    return dp[-1][-1]

1
2
3
4
5
6
7
8

def change(self, amount: int, coins: List[int]) -> int:
f = [0 for _ in range(amount + 1)]
f[0] = 1
for c in coins:
    for j in range(c, amount + 1):
        f[j] = f[j] + f[j - c]

return f[amount]

1
2
3
4
5
6
7
8

def combinationSum4(self, nums: List[int], target: int) -> int:
	f = [0 for _ in range(target + 1)]
	f[0] = 1
	for j in range(1, target + 1):
	    for n in nums:
	        if j >= n:
	            f[j] += f[j - n]
	return f[target]