动态规划-分割类问题

分割类问题也算是动态规划的常客。对于字符类问题,状态转移方式往往依赖于相邻的位置。

0-1背包问题,状态方程不仅依赖于相邻的位置,还依赖于满足条件的空间位置。

对于分割类型题,动态规划的状态转移方程通常并不依赖相邻的位置,而是依赖于满足分割条件的位置。

阅读更多

动态规划-股票交易问题

类型特点

股票买卖类问题的「状态」有三个,第一个是天数,第二个是允许交易的最大次数,第三个是当前的持有状态(即之前说的 rest 的状态,我们不妨用 1 表示持有,0 表示没有持有)。然后我们用一个三维数组就可以装下这几种状态的全部组合:

1
2
3
4
5
6
7
8
9
dp[i][k][0 or 1]
0 <= i <= n - 1, 1 <= k <= K
n 为天数,大 K 为交易数的上限,01 代表是否持有股票。
此问题共 n × K × 2 种状态,全部穷举就能搞定。

for 0 <= i < n:
for 1 <= k <= K:
for s in {0, 1}:
dp[i][k][s] = max(buy, sell, rest)
阅读更多

动态规划-背包问题

三种背包问题

背包问题主要分为三种:

  • 0-1 背包问题:
    • 定义:给你一个可装载重量为 W 的背包和 N 个物品,每个物品有重量和价值两个属性。其中第 i 个物品的重量为 wt[i],价值为 val[i],现在让你用这个背包装物品,最多能装的价值是多少?
    • 变种的子集背包问题定义:给一个可装载重量为 sum / 2 的背包和 N 个物品,每个物品的重量为 nums[i]。现在让你装物品,是否存在一种装法,能够恰好将背包装满?
  • 完全背包问题:
    • 定义:0-1 背包问题中,每个物品最多可以装一次。完全背包中,所有物品的数量是无限的。
    • 因为物品的数量没有限制,因此使用基于贪心策略来做。 循环判断「剩余空间下可容纳的最高性价比物品」,并加入背包。
阅读更多

动态规划-子串子序列类型

定义

根据 Leetcode 的习惯,子序列(subsequence)不必连续,子数组(subarray)或子字符串(substring)必须连续。

动态规划中,子串子序列的问题大概分为如下几种:

阅读更多