动态规划一
6/6
T416 分割等和子集
1、这一题可以先简化如下： //先加一遍成为总和，若为奇数，返回false，若为偶数，设置目标和为二分之一 //问题简化为：是否可以取出部分元素，使得和恰好等于目标和 //dp[i]：容量为i的情况下能出现的最大值
2、有一个有些绕的点：本题重量等于价值。如果背包所载重量为target， dp[target]就是装满 背包之后的总价值，因为 本题中每一个元素的数值既是重量，也是价值，所以，当 dp[target] == target 的时候，背包就装满了。
3、代码如下：
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
// dp[i]中的i表示背包内总和
// 题目中说：每个数组中的元素不会超过 100，数组的大小不会超过 200
// 总和不会大于20000，背包最大只需要其中一半，所以10001大小就可以了
vector<int> dp(10001, 0);
for (int i = 0; i < nums.size(); i++) {
sum += nums[i];
}
// 也可以使用库函数一步求和
// int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum % 2 == 1) return false;
int target = sum / 2;
// 开始 01背包
for(int i = 0; i < nums.size(); i++) {
for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入，所以从大到小遍历
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
}
}
// 集合中的元素正好可以凑成总和target
if (dp[target] == target) return true;
return false;
}
};
【0/1背包问题】（摘录）
不放物品i：背包容量为j，里面不放物品i的最大价值是dp[i - 1][j]
放物品i：背包空出物品i的容量后，背包容量为j - weight[i]，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]且不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值
递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
初始化： for (int i = 1; i < weight.size(); i++) { // 当然这一步，如果把dp数组预先初始化为0了，这一步就可以省略，但很多同学应该没有想清楚这一点。 dp[i][0] = 0; } // 正序遍历 for (int j = weight[0]; j <= bagweight; j++) { dp[0][j] = value[0]; }
一维dp数组（滚动数组） 对于背包问题其实状态都是可以压缩的。
在使用二维数组的时候，递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]); 与其把dp[i - 1]这一层拷贝到dp[i]上，不如只用一个一维数组了，只用dp[j]（一维数组，也可以理解是一个滚动数组）。
这就是滚动数组的由来，需要满足的条件是上一层可以重复利用，直接拷贝到当前层。 读到这里估计大家都忘了 dp[i][j]里的i和j表达的是什么了，i是物品，j是背包容量。
dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
一维dp数组，其实就上上一层 dp[i-1] 这一层 拷贝的 dp[i]来。 所以在 上面递推公式的基础上，去掉i这个维度就好。 递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
以下为分析： dp[j]为 容量为j的背包所背的最大价值。 dp[j]可以通过dp[j - weight[i]]推导出来，dp[j - weight[i]]表示容量为j - weight[i]的背包所背的最大价值。 dp[j - weight[i]] + value[i] 表示 容量为 [j - 物品i重量] 的背包 加上 物品i的价值。（也就是容量为j的背包，放入物品i了之后的价值即：dp[j]） 此时dp[j]有两个选择，一个是取自己dp[j] 相当于 二维dp数组中的dp[i-1][j]，即不放物品i，一个是取dp[j - weight[i]] + value[i]，即放物品i，指定是取最大的，毕竟是求最大价值，
所以递归公式为： dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
可以看出相对于二维dp数组的写法，就是把dp[i][j]中i的维度去掉了。
一维dp数组如何初始化 关于初始化，一定要和dp数组的定义吻合，否则到递推公式的时候就会越来越乱。 dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]，那么dp[0]就应该是0，因为背包容量为0所背的物品的最大价值就是0。
看一下递归公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。
这样才能让dp数组在递归公式的过程中取的最大的价值，而不是被初始值覆盖了。 那么假设物品价值都是大于0的，所以dp数组初始化的时候，都初始为0就可以了。
一维dp数组遍历顺序 代码如下： for(int i = 0; i < weight.size(); i++) { // 遍历物品 for(int j = bagWeight; j >= weight[i]; j–) { // 遍历背包容量 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); } }
二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。 为什么呢？ 倒序遍历是为了保证物品i只被放入一次。但如果一旦正序遍历了，那么物品0就会被重复加入多次！
举例：物品0的重量weight[0] = 1，价值value[0] = 15 如果正序遍历 dp[1] = dp[1 - weight[0]] + value[0] = 15 dp[2] = dp[2 - weight[0]] + value[0] = 30 此时dp[2]就已经是30了，意味着物品0，被放入了两次，所以不能正序遍历。
为什么倒序遍历，就可以保证物品只放入一次呢？ 倒序就是先算dp[2] dp[2] = dp[2 - weight[0]] + value[0] = 15 （dp数组已经都初始化为0） dp[1] = dp[1 - weight[0]] + value[0] = 15 所以从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了。
6/5
T96 不同的二叉搜索树
1、这一题看起来有点难，但靠举例+逻辑推理纯手搓AC啦
2、关键：吸取上一题教训+看到n最大值只有19后，意识到这一题也可以采取全覆盖遍历+动态规划的解法，也就是当根节点取不同值时，每个值天然将左右子树区分为两组节点，这些节点内在又具备逐个加一的统一有序规律性，因此可以直接等价为同样节点数目的二叉搜索树数目值（即便所有节点的值都统一加了K）。这样一来，新的dp[i]在遍历中不断根据左右子树的二叉搜索树数目乘积累增即可
3、代码如下：
class Solution {
public:
int numTrees(int n) {
vector<int> dp(n+5,0);
dp[0] = 1;
dp[1] = 1;
dp[2] = 2;
if(n <= 2)
return dp[n];
for(int i = 3;i <= n;i++){
for(int j = 0;j <= i-1;j++){
dp[i] = dp[i] + dp[j] * dp[i-1-j];
}
}
return dp[n];
}
};
4、这一题和上一题都有一个细节需注意： vector
T343 整数拆分
1、这一题我一开始想了很久，没找到巧妙的方法，看了题解后才知道核心就是利用已有计算量的遍历，不存在什么数学上的简易解法。
2、关键：对于每个特定的数，可以选择拆分/不拆分，其中不拆分多一种拆分里不存在的解，因此要考虑max取值。例如，3的拆分可以是1x1x1 1x2 但没有3；5的拆分可以是1x4 1x2x2 2x3但没有5，这两组值不一定谁比谁大。
3、代码如下：
class Solution {
public:
int integerBreak(int n) {
vector<int> dp(n + 1, 0);
dp[2] = 1;
for (int i = 3; i <= n; i++) {
for (int j = 1; j < i; j++) {
dp[i] = max(
dp[i],
max(
j * (i - j), // 只拆成两个数
j * dp[i - j] // 右边继续拆
)
);
}
}
return dp[n];
}
};
4、这一题有极其严苛的较难的数学证明法、动态规划优化法和基于高等数学函数极值证明的贪心算法，在所有专题刷完后可进行拓展
6/4
T63 不同路径二
1、这一题不能用数学公式解决了，因为新增了障碍物
2、三个关键：首先，第一行第一列如果中途遇到障碍物，后续格子无法左移/上移，因此无法绕开障碍物，值依旧是0；其次，dp遍历时遇到障碍物就要设置0，再做比较；最后，开头的[0][0]也要当心有障碍物
3、完整代码如下：
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector<vector<int>> dp(
m,
vector<int>(n, 0)
);
if(obstacleGrid[0][0] == 1)
return 0;
dp[0][0] = 1;
// 第一列
for(int i = 1; i < m; i++)
{
if(obstacleGrid[i][0] == 1)
dp[i][0] = 0;
else
dp[i][0] = dp[i - 1][0];
}
// 第一行
for(int j = 1; j < n; j++)
{
if(obstacleGrid[0][j] == 1)
dp[0][j] = 0;
else
dp[0][j] = dp[0][j - 1];
}
for(int i = 1; i < m; i++)
{
for(int j = 1; j < n; j++)
{
if(obstacleGrid[i][j] == 1)
{
dp[i][j] = 0;
}
else
{
dp[i][j] =
dp[i - 1][j]
+
dp[i][j - 1];
}
}
}
return dp[m - 1][n - 1];
}
};
T62 不同路径
1、注意行列不要反，以及二维数组动态非固定住要用vector，语法有些复杂，需要初始化
2、赋值时一定保证之前的值是计算过的，遍历前需要把左侧、上侧网格统一赋值
3、代码如下：
class Solution {
public:
int uniquePaths(int m, int n) {
//本质上是在n-1次右移中插入m-1次下移，应该有数学公式可以直接计算得出
//动态规划解法：dp[i][j]代表从左上角（0，0）到（i,j）处的路径总数
vector<vector<int>> dp(m,vector<int>(n,0));
dp[0][0] = 1;
for(int i = 1;i < m;i++){
dp[i][0] = 1;
}
for(int i = 1;i < n;i++){
dp[0][i] = 1;
}
for(int i = 1;i < m;i++){
for(int j = 1;j < n;j++){
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
};
4、这一题也可以等效为高中数学组合题，将两种走法加起来再取组合就好理解了。
从左上角到右下角，必须走：
向下 m-1 次 向右 n-1 次
总共走：
m+n-2 步
问题变成： 在 m+n-2 个位置中，选择 m-1 个位置放“向下”，其余自动是“向右”。 因此答案就是组合数：
例如：
m=3,n=7
需要：
↓↓ →→→→→→
共：
8步
从 8 个位置里选 2 个放 ↓：
直接阶乘会溢出：
(n+m-2)!
非常大。 因此边乘边除：
class Solution {
public:
int uniquePaths(int m, int n) {
long long ans = 1;
int k = min(m - 1, n - 1);
for(int i = 1; i <= k; i++)
{
ans = ans * (m + n - 2 - k + i) / i;
}
return (int)ans;
}
};5、这里阶乘的处理方式很重要，有必要把复杂度高的数学计算统一学习理解最优解
6/3
T746 使用最小花费爬楼梯
1、这一题也手搓AC啦，中途遇到了一个小bug：忘记0...n实际上是n+1个元素，因此dp数组大小要开n+1
2、注意n的来源cost.size();语法；注意CPP自带许多库，最小值可用min()语法
3、代码如下：
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
vector<int>dp(n+1);
//dp[i]:爬到下标为i的台阶的最小花费
if(n <= 1)
return 0;
dp[0] = 0;
dp[1] = 0;
for(int i = 2;i <= n;i++){
dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
}
return dp[n];
}
};
T70 爬楼梯
1、太经典了，高中数学题。上一层的解数目+上二层的解数目。手搓直接AC，注意一下两个语法点：vector
2、代码如下：
class Solution {
public:
int climbStairs(int n) {
vector<int> dp(n+1);
if(n == 1)
return 1;
dp[1] = 1;
dp[2] = 2;
for(int i = 3;i <= n;i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
};
6/2
T509 斐波那契数
1、从这题开始，所有解法都手搓啦～
2、直接按递推公式写的代码AC了，但耗时较长：
class Solution {
public:
int fib(int n) {
if(n>=2)
return fib(n-1) + fib(n-2);
else if(n==1)
return 1;
else
return 0;
}
};
3、耗时最短的解法如下：
class Solution {
public:
int fib(int N) {
if (N <= 1) return N;
vector<int> dp(N + 1);
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= N; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[N];
}
};
我们可以借此清晰学习到方才的五部曲： 动规五部曲： 这里我们要用一个一维dp数组来保存递归的结果 确定dp数组以及下标的含义 dp[i]的定义为：第i个数的斐波那契数值是dp[i] 确定递推公式 为什么这是一道非常简单的入门题目呢？ 因为题目已经把递推公式直接给我们了：状态转移方程 dp[i] = dp[i - 1] + dp[i - 2]; dp数组如何初始化 题目中把如何初始化也直接给我们了，如下： dp[0] = 0; dp[1] = 1;
确定遍历顺序 从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的 举例推导dp数组 按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2]，我们来推导一下，当N为10的时候，dp数组应该是如下的数列： 0 1 1 2 3 5 8 13 21 34 55 如果代码写出来，发现结果不对，就把dp数组打印出来看看和我们推导的数列是不是一致的。 以上我们用动规的方法分析完了，C++代码如下：
class Solution {
public:
int fib(int N) {
if (N <= 1) return N;
vector<int> dp(N + 1);
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= N; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[N];
}
};
时间复杂度：O(n) 空间复杂度：O(n) 4、然而，这样空间复杂度就上来了，所以随想录里提供了更进一步的优化（不新建数组）：
class Solution {
public:
int fib(int N) {
if (N <= 1) return N;
int dp[2];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= N; i++) {
int sum = dp[0] + dp[1];
dp[0] = dp[1];
dp[1] = sum;
}
return dp[1];
}
};
5、分析最初解法耗时较长原因：展开时做了很多重复运算，没能把一个计算循环利用。例如： fib(5)展开后，会出现下图待计算值，可以观察到fib(3)、fib(2)等都被重复计算了许多遍。变成了平方级别的时间复杂度，不适用大型数值计算。 fib(5) ├─ fib(4) │ ├─ fib(3) │ │ ├─ fib(2) │ │ └─ fib(1) │ └─ fib(2) └─ fib(3) ├─ fib(2) └─ fib(1)
【动态规划专题】
（摘录）对于动态规划问题，拆解为如下五步曲 确定dp数组（dp table）以及下标的含义 确定递推公式 dp数组如何初始化 确定遍历顺序 举例推导dp数组
T968 监控二叉树
1、这一题最关键的是从下往上处理，直接从叶节点的父节点开始，依次向上遍历。这个思路看起来不难，然而不好想到，因为正确性证明过于模糊，看似经不起直觉验证。
2、精简代码如下（含递归）：
class Solution {
private:
int result;
int traversal(TreeNode* cur) {
if (cur == NULL) return 2;
int left = traversal(cur->left); // 左
int right = traversal(cur->right); // 右
if (left == 2 && right == 2) return 0;
else if (left == 0 || right == 0) {
result++;
return 1;
} else return 2;
}
public:
int minCameraCover(TreeNode* root) {
result = 0;
if (traversal(root) == 0) { // root 无覆盖
result++;
}
return result;
}
};
3、返回值含义： 0：当前节点无覆盖 1：当前节点有摄像头 2：当前节点已被覆盖，但没有摄像头
4、此题还要动态规划解法和正确性证明，待刷完动态规划专题后补充第二种解法及证明
6/1
T738 单调递增的数字
1、这一题我秉承尽可能让数字大一点（优先保高位）的思路，伪代码如下： //38432152 //从最左位开始，观察第二个数若大于等于它，看能否保持这个值直到不满足（下一个小于了）；若第二个数就小于了，最左侧减1，其他位都设置为9 //把之前那一串一样的数字（除最左位，也可能除其他，例如3456662的45）全部下降1（只下降连续段最左侧也可以，后面的反正都要被覆盖），若还大于等于最左侧的数，直接只保留左数第二位，其他位全部设置成9；若小于最左侧的数，最左侧减1，其他位置全部设置为9 //清除前置零
2、简单优化：不必拆开最左位单独考虑，把它融为一体即可，10、332依旧符合该逻辑，都是连续段不符合下一个后最左侧连续点下降1，其他赋值9
3、代码如下：
class Solution {
public:
int monotoneIncreasingDigits(int n) {
string s = to_string(n);
int i = 0;
while(i < s.size() - 1)
{
// 发现下降
if(s[i] > s[i + 1])
{
// 找到前面连续相同数字的最左位置
int j = i;
while(j > 0 && s[j] == s[j - 1])
{
j--;
}
// 该位置减1
s[j]--;
// 后面全部变9
for(int k = j + 1; k < s.size(); k++)
{
s[k] = '9';
}
break;
}
i++;
}
// 清除前导0
return stoi(s);
}
};
4、有时间可以尝试一下从后往前的遍历
T56 合并区间（这一题好多企业考，可能因为应用场景广泛）
1、我的初始思路是： //先按照每个区间的右侧从小到大排序，取最小的右侧值k //检测第二个排序区间的左侧是否小于等于k，若小于，更新k为这个区间的右侧值，合并区间，左侧选两个左侧的最小值 //用新K处理第三个排序区间，循环，直到处理完毕
2、成功踩坑几个点：首先，不合并也要更新K值为第二个区间的右侧，否则信息滞后；其次，这样处理后可能有遗留未合并区间，需要记录changed布尔值带一个while——[[2,3],[4,5],[1,10]]这种在第一轮就会合并为重叠的[2,3],[1,10]；最后，时间复杂度较高，代码也较为复杂。
3、初始代码如下，可以AC：
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
bool changed = true;
while (changed) {
changed = false;
// 按右端点排序
sort(
intervals.begin(),
intervals.end(),
[](const vector<int>& a, const vector<int>& b) {
return a[1] < b[1];
}
);
vector<vector<int>> next;
int i = 0;
while (i < intervals.size()) {
// 尝试与后一个区间合并
if (
i + 1 < intervals.size() &&
intervals[i + 1][0] <= intervals[i][1]
) {
next.push_back({
min(intervals[i][0], intervals[i + 1][0]),
max(intervals[i][1], intervals[i + 1][1])
});
changed = true;
i += 2;
}
else {
next.push_back(intervals[i]);
i++;
}
}
intervals = next;
}
return intervals;
}
};
4、最优解代码如下：
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>> result;
if (intervals.size() == 0) return result; // 区间集合为空直接返回
// 排序的参数使用了lambda表达式
sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});
// 第一个区间就可以放进结果集里，后面如果重叠，在result上直接合并
result.push_back(intervals[0]);
for (int i = 1; i < intervals.size(); i++) {
if (result.back()[1] >= intervals[i][0]) { // 发现重叠区间
// 合并区间，只更新右边界就好，因为result.back()的左边界一定是最小值，因为我们按照左边界排序的
result.back()[1] = max(result.back()[1], intervals[i][1]);
} else {
result.push_back(intervals[i]); // 区间不重叠
}
}
return result;
}
};
5、关键：我们可以发现，这题是否最优主要在于是否可以一个循环遍历合并完所有区间，而非左右排序之分。右侧排序也是可以的，但相对应就应该由右侧往左侧遍历，左侧排序则左侧往右侧遍历，两者都要对比max/min值更新新区间边界和对比边界。核心：往前进方向遍历时，已处理的区间必须保证安心作为孤岛，即后续边界均可控制不与之重合。
对应的右侧排序右遍历代码也可以AC：
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>> result;
if(intervals.empty())
return result;
// 按右端点从小到大排序
sort(
intervals.begin(),
intervals.end(),
[](const vector<int>& a,const vector<int>& b)
{
return a[1] < b[1];
}
);
// 从最后一个区间开始
result.push_back(intervals.back());
for(int i = intervals.size() - 2; i >= 0; i--)
{
// 当前区间与已合并区间重叠
if(intervals[i][1] >= result.back()[0])
{
// 只更新左边界即可
// 因为 result.back()[1]
// 一定是当前最大的右边界
result.back()[0] =
min(
result.back()[0],
intervals[i][0]
);
}
else
{
result.push_back(intervals[i]);
}
}
return result;
}
};
T763 划分字母区间
1、思路经典：每次取符合要求的最短片段，其他取法不能更优，故最终为片段数最多的解
2、关键：每新遍历一个char，必须更新right为当前已遍历所有char的最大终止界限，否则会出现将同一字母切分到不同片段的情景
3、待选切割点：每个char出现的最后位置
4、代码如下：
class Solution {
public:
vector<int> partitionLabels(string S) {
int hash[26] = {0}; // i为字符，hash[i]为字符出现的最后位置
for (int i = 0; i < S.size(); i++) { // 统计每一个字符最后出现的位置
hash[S[i] - 'a'] = i;
}
vector<int> result;
int left = 0;
int right = 0;
for (int i = 0; i < S.size(); i++) {
right = max(right, hash[S[i] - 'a']); // 找到字符出现的最远边界
if (i == right) {
result.push_back(right - left + 1);
left = i + 1;
}
}
return result;
}
};