动态规划-分割类问题

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

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)必须连续。

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

阅读更多

排列-组合-子集算法总结

概念

组合、排列、子集是 leetcode 中比较常见的题目系列,主要区别在于:

名称 概念 示例题目
排列 每项结果有序,即[1,2] 与 [2,1]是两个结果 46. 全排列47. 全排列 II
组合 每项结果无序,即[1,2]与[2,1]是一个结果 39. 组合总和216. 组合总和 III40. 组合总和 II77. 组合
子集 与组合类似,但会有额外的限制,比如数量等 78. 子集90. 子集 II

排列与组合

阅读更多

二叉树总结

基本概念

二叉树最重要的概念应该是:前序遍历、中序遍历、后续遍历 了。

  • 前序遍历:根节点->左子树->右子树(根->左->右)
  • 中序遍历:左子树->根节点->右子树(左->根->右)
  • 后序遍历:左子树->右子树->根节点(左->右->根)
  • 层序遍历: 从上至下、从左至右层次进行,借助队列实现。
阅读更多