fucking-algorithm
fucking-algorithm copied to clipboard
labuladong
经典动态规划：子集背包问题 :: labuladong的算法小抄
唯一需要注意的是 j 应该从后往前反向遍历，因为每个物品（或者说数字）只能用一次，以免之前的结果影响其他的结果。
这句话没读懂啊，为啥会影响之前的其他结果？ 为啥原来二维数组不用反向遍历？二维数组不能反过来遍历吧，前一个值都没有算出来，反过来不就不能利用上一个计算出来的值了吗？
唯一需要注意的是 j 应该从后往前反向遍历，因为每个物品（或者说数字）只能用一次，以免之前的结果影响其他的结果。
这句话没读懂啊，为啥会影响之前的其他结果？ 为啥原来二维数组不用反向遍历？二维数组不能反过来遍历吧，前一个值都没有算出来，反过来不就不能利用上一个计算出来的值了吗？
qs,我也想知道
個人理解 不確定是不是正確 :)
觀察2D 是依據前一排 i-1 得出的 (like dp[i-1][j] ), 而第一排其實是 Base case ( dp[0: i][0] = true, dp[0][1: halfSum] = false) 所以才能得出下一排的解答.
轉成1D 要反轉是因為 dp[ j - nums[i-1]], 原本2D要取 "上一排" 比 j 小的值. 但是1D如果從 j =1開始, 1D array前方的值就會被改變，後方再取 j - nums[i-1] 就變成 updated過的值, 而從後方開始就可以避免這個問題.
还是没理解。尝试按之前的遍历方向那篇博文 https://labuladong.gitee.io/algo/3/24/71/
画了矩阵图，dp[i][j] 来自于 dp[i-1][j]和 dp[i-1][j-nums[i]] ，那篇博文dp[i][j]来自dp[i-1][j] 和dp[i-1][j-1]、dp[i][j-1]，博文说要正向遍历 因为，这样每一步迭代的左边、上边、左上边的位置都是 base case 或者之前计算过的，而且最终结束在我们想要的答案 dp[m][n]。
我画了图，这道题的情况base case 和它相同，方向也一致，为什么这个就是从右到左了，画图的时候怎么区别这种情况呢？
还是没理解。尝试按之前的遍历方向那篇博文 https://labuladong.gitee.io/algo/3/24/71/
画了矩阵图，dp[i][j] 来自于 dp[i-1][j]和 dp[i-1][j-nums[i]] ，那篇博文dp[i][j]来自dp[i-1][j] 和dp[i-1][j-1]、dp[i][j-1]，博文说要正向遍历 因为，这样每一步迭代的左边、上边、左上边的位置都是 base case 或者之前计算过的，而且最终结束在我们想要的答案 dp[m][n]。
我画了图，这道题的情况base case 和它相同，方向也一致，为什么这个就是从右到左了，画图的时候怎么区别这种情况呢？
注意： 这个方向不是固定的 一定要弄清楚 当前的状态依赖于从哪个方向传递过来的前一个状态， 比如 如果 i状态依赖于 从 m方向传递过来的 这种情况你所说的 每一步迭代依赖位置就不一样了
@zhongweiLeex 我判断方向错了吗？我画出来两个方向都是左上到右下。区别在于倾斜度不同，为什么一个需要反方向遍历，一个不用呢？
建议再读一下，东哥公众号 labuladong 的 动态规划答疑这篇文章， 关于dp方向，讲的蛮清楚的。！
@Tokics 楼上大佬们解释得很清晰啦，我再来补充点看会不会更具体些？
1.先看原来2D情况，dp[i][j]的值，都是仅依靠上一行dp[i-1][...]得出的。意思是我们要算当前dp[i]行的值，仅需要上一行dp[i-1]就好。所以可以将其转化为：原地更新1D数组问题；
2.现在考虑降为1D，定义该1D数组为int[] dp。回忆原来2D情况，dp[i][j]的值都是依靠“其正上方的值dp[i-1][j]+左上方的值dp[i-1][j-nums[i]]”来更新。那么如果对1D进行正向遍历即从dp[0]->dp[n-1]填充，对于某一位例如dp[cur]的更新，势必会用到dp[pre]（pre<cur），因为是正向遍历，那么dp[pre]在当前轮次已经被更新过了，当在这种情况下计算的dp[cur]肯定不正确（其实说白了，就相当于2D情况下，使用了同一行的值。例如使用dp[i][j-nums[i]]来更新dp[i][j]）；
3.现在解释对1D数组进行反向遍历即从dp[n-1]->dp[0]填充。同样，对于某一位例如dp[cur]的更新，势必会用到dp[pre]（pre<cur）。但注意，因为是从后往前进行遍历的，此时dp[pre]在当前轮次未被更新，所以就相当于2D情况下使用的上一行的值，这样计算就是正确的了。
@labuladong 我觉得动态规划问题用递归（自顶而下）的时间复杂度是不是天生要比迭代（自底而上）高啊？（递归在参数传递的时候会有额外的时空开销），或者这些开销相对于整体可以忽略不计？ 这个想法来源是东哥在前几节动态规划子序列问题，我解题时的个人感觉，字符串其实可以穿拷贝的，oj也是能通的过，当然传引用的效率更高这是可以理解的。 🙏🙏🙏
在这题中我也有同样的感觉（这个oj超时了） 我个人感觉这个问题不能用备忘录优化的（菜狗） 416 c++
class Solution {
public:
// 定义dp为在前i个数据中挑数累加, 直到结果等于总和的一半
// sum从0开始选数求和，直到等于总和的一半
bool dp(vector<int>& nums, int i, int sum, int cap ）// cap为总和的一半
{
if(sum == cap)
return true;
if(i == -1)
return false;
return dp(nums, i-1, sum, cap)||dp(nums, i-1, sum+nums[i], cap);
}
bool canPartition(vector<int>& nums) {
int cap = accumulate(nums.begin(), nums.end(), 0);
if(cap%2 == 1)
return false;
return dp(nums, nums.size()-1, 0, cap/2);
}
};
PS：再引申一个问题，动态规划能用递归做应该也能用迭代做，所以会不会有哪些情况或特殊的问题下这两种方法有优劣之分呢？ 求东哥解惑🙏
@kuangkuangkuangha 首先给你的思考点赞~
1、你给出的这个解法，本质上不是动态规划思路，而是回溯算法思路，暴力尝试所有可能的累加和，所以当然会超时。
动态规划的关键在于「状态转移方程」，即如何通过若干个已计算出的「状态」推导出未计算的「状态」，在这个推导「状态」的过程中，可能存在重复计算「状态」的情况（重叠子问题），需要备忘录技巧消除冗余计算。进一步，备忘录可以改造成 dp 数组，用非递归的方式进行状态转移，也就是自底向上的动态规划解法。
那么看看你给出的代码，虽然函数名字叫 dp，但你是否能够找到这个函数在递归过程中在不断变化的「状态」？也许你会说参数 i 和 sum 在变化，可以把他们看做「状态」，嗯，这没问题，但问题是你是否能够通过已经计算出来的「状态」推导出未计算的状态？答案是不行。
比如就按照你的定义，比如说 dp(i) == false，那我知道 nums[0..i] 不能凑出目标和 cap，但这个结论能复用吗？你能通过 dp(i) == false 推出 dp(i + 1) 等于多少吗？不能，还得老老实实从头穷举 nums[0..i+1] 能不能凑出 cap。
所以，你的这个解法思路是回溯算法，改写成如下形式看起来更明显：
bool backtrack(vector<int>& nums, int i, int trackSum, int cap ) {
if(trackSum == cap)
return true;
if(i == -1)
return false;
// 做选择
trackSum += 0;
backtrack(nums, i - 1, trackSum, cap)
// 撤销选择
trackSum -= 0;
// 做选择
trackSum += nums[i];
backtrack(nums, i - 1, trackSum, cap);
// 撤销选择
trackSum -= nums[i];
}
2、动态规划用于优化暴力穷举解法所用的备忘录 memo 中的内容其实就是 dp 数组的内容，大部分情况他们的理论效率相同，至于你说的递归参数的问题，从 Big O 表示法 的角度来看是可以忽略不计的。特殊情况是有的，比如改成迭代之后可以应用 空间压缩技巧 优化空间复杂度；再比如状态转移设计不合理的情况下，可能你只能写出递归解法，却无法写出迭代解法。
以上是我个人的一些理解，我觉得你提出的这个问题很有价值，后续考虑专门写篇文章写一写动态规划和回溯算法在思路上的区别。如果你还有什么问题，欢迎继续和我探讨~
@labuladong 感谢东哥的指导🙏🙏，您的点拨确实让我有了很大的启发，我逐渐感觉状态确实是此类问题的题眼，含有base case在不同场景下的初始化也是个难点，等我把东哥这系列文章都看完，看看会不会有通俗一些的理解。再次感谢东哥，感谢开源🙏
@KaiKangSDU 这个问题很好，698 题需要 经典回溯算法：集合划分问题 使用的回溯算法技巧解决，我认为这两道题的区别在于：
416 题 将集合分成两个相等子集，相当于问你如何装满一个容量为 sum / 2 的背包，这是标准的背包问题。
但 698 题让你将集合分成 k 个相等的子集，也就是每个子集元素之和为 sum / k。对于某一个子集来说，可以把问题转化为装满容量为 sum / k 的背包问题，但问题在于你要同时保证其他的 k - 1 个子集元素之和也都是 sum / k，那么这就无法用标准的背包问题思路求解了，只好用回溯算法的暴力穷举一个个尝试。
贴一个自顶向下带个备忘录C++
bool dp(vector<int>& nums, int i, int size) {
// base case
int j = size;
if (size == 0) return true; // 背包被装满了，返回true
if (i == -1) return false; // 没有可以选择的数字，因此不可能装满
if (memo[i][j] != -1) return memo[i][j];
if (size - nums[i] >= 0) {
return memo[i][j] = dp(nums, i - 1, size) || dp(nums, i - 1, size - nums[i]); // dp(nums, i - 1, size)：判断不放nums[i]能否将size装满; dp(nums, i - 1, size - nums[i]) 放nums[i]的话判断是否在[1, i - 1]这些数字中将size - nums[i]装满
} else {
return memo[i][j] = dp(nums, i - 1, size);
}
}
bool canPartition(vector<int>& nums) {
int n = nums.size();
int sum = 0;
for (auto num: nums) {
sum += num;
}
if (sum % 2 != 0) return false; // 无法分割
int size = sum / 2;
memo.assign(n, vector<int> (size + 1, -1)); // 重量从0到sum / 2;
return dp(nums, n - 1, sum / 2);
}
};
记忆化搜索Java版本：
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
}
if (sum % 2 != 0) return false;
memo = new Boolean[sum / 2 + 1][nums.length];
return process(nums, sum / 2, 0);
}
Boolean[][] memo;
public boolean process(int[] nums, int bag, int index) {
if (index < 0 || index >= nums.length) {
return false;
}
if (bag == 0) {
return true;
} else if (bag < 0) {
return false;
}
if (memo[bag][index] != null) {
return memo[bag][index];
}
memo[bag][index] = process(nums, bag - nums[index], index + 1)
|| process(nums, bag, index + 1);
return memo[bag][index];
}
}
我觉得递归和递推的区别有两个：
- 递归不用考虑顺序，如果加上备忘录，就会把每一个算一遍，不会漏也不会重复；
- 递归空间占用大，容易运行错误，也就是“爆栈”。
二维压缩到一维，一般是指保留一行，去掉其他行。 》当前的（i，j）只利用到了 上一行的 （i-1，j）与（i-1, j-num[j]）
假设 j为5， j-num[j]为3， 则 第i-1行：x x x 3 x 5 第i行： x x x x x x
在一维的情形下：所以如果j是从0向上增长的话，第i-1行的3已经更新了（被第i行） ， 等到计算第i行的5 用到的（i-1, j-num[j]）其实已经变为（i, j-num[j]）
综上所述，从大到小遍历才不会出问题。
Python解法
class Solution:
def canPartition(self, nums: List[int]) -> bool:
n = len(nums)
Sum = sum(nums)
if Sum % 2 != 0:
return False
Sum = Sum // 2 # bag capacity
# 对于前i个物品，背包的容量为j
# dp[i][j] = true能恰好装满，false不能恰好装满
dp = [[False for _ in range(Sum+1)] for __ in range(n+1)]
# base case：背包容量为0时，什么都不装也已经装满了
for i in range(n+1):
dp[i][0] = True
# 对于每一个新加入的元素nums[i-1]循环
for i in range(1, n+1):
# 对于1到Sum中每一个背包容量，判断能否正好装满
for j in range(1, Sum+1):
# 背包容量不足，不装入第i个物品
# 此时能否装满的判断，等于没有加入元素nums[i-1]时的状态
if j - nums[i-1] < 0:
dp[i][j] = dp[i-1][j]
# 容量足够，对nums[i-1]有两个选择：
# 装入nums[i-1]，能否恰巧装满取决于dp[i-1][j-nums[i-1]]的状态
# 不装nums[i-1]，能否装满取决于dp[i-1][j]的状态
else:
dp[i][j] = dp[i-1][j-nums[i-1]] or dp[i-1][j]
return dp[n][Sum]
