fucking-algorithm
fucking-algorithm copied to clipboard
labuladong
对动态规划进行降维打击 :: labuladong的算法小抄
一脸懵逼的看完了。。。for (int j = i + 1; j < n; j++) {这里跟j=i+1初始条件没有任何关系。外层循环第一行定义一个变量，内层循环最后一行对这个变量赋值，这个变量就是i+1，j-1的值。循环条件是i--，j++
看懂啦!谢谢东哥的空间压缩~! 小而精的那块,就是i不是原先表达第i层嘛,j从左到右遍历,比如现在在遍历j,当前的j会被记录,这个dp[i][j]其实i自下而上的上一层的遗留数据,我们在用当前数据覆盖它之前将其保留,再进行下一轮内层for循环的时候,那个prev其实就是dp[i+1][j-1],而dp[j],当前还没覆盖呢,所以是下一层填数据时的老数据,即dp[i+1][j],dp[j-1]已经在处理j处的元素之前了,所以它是本轮(i)层的数据,就是dp[i][j-1],所以就都考虑到了.就想在一维数组上一直对老值做修改形成一个滚动的效果
东哥你好，对于文中这一句如果计算状态 dp[i][j] 需要的都是 dp[i][j] 相邻的状态，那么就可以使用空间压缩技巧有点疑惑，能不能进行空间压缩只是看dp[i][j]是否依赖dp这个二维数组中的相邻位置吗？
因为今天在做leetcode 1049 最后一块石头的重量时，写出了二维dp，代码如下：
class Solution {
public int lastStoneWeightII(int[] stones) {
if (stones.length == 1) {
return stones[0];
} else if (stones.length == 2) {
return Math.abs(stones[0] - stones[1]);
}
return dp(stones);
}
public int dp(int[] stones) {
int sum = 0;
for (int stone : stones) {
sum += stone;
}
int half = sum / 2;
int[][] dp = new int[stones.length + 1][half + 1];
Arrays.fill(dp[stones.length], 0);
for (int i = stones.length - 1; i >= 0; i--) {
for (int j = half; j >= 0; j--) {
int p1 = dp[i + 1][j];
int p2 = 0;
if (stones[i] <= j) {
p2 = stones[i] + dp[i + 1][j - stones[i]];
}
dp[i][j] = Math.max(p1, p2);
}
}
return sum - dp[0][half] * 2;
}
}
然后抽出主要逻辑：
int p1 = dp[i + 1][j];
int p2 = 0;
if (stones[i] <= j) {
p2 = stones[i] + dp[i + 1][j - stones[i]];
}
dp[i][j] = Math.max(p1, p2);
我写到这里二维数组就停下了，因为我觉得dp[i + 1][j - stones[i]]与dp[i][j]需不需要不好说，而且就算需要还不一定相邻，所以就没有想着改成一维数组，但是我看评论代码随想录的评论，是写出了一维数组的代码：
class Solution {
public int lastStoneWeightII(int[] stones) {
int sum = 0;
for (int i : stones) {
sum += i;
}
int target = sum >> 1;
//初始化dp数组
int[] dp = new int[target + 1];
for (int i = 0; i < stones.length; i++) {
//采用倒序
for (int j = target; j >= stones[i]; j--) {
//两种情况，要么放，要么不放
dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
}
}
return sum - 2 * dp[target];
}
}
dp[i][j]需要dp[i+1][j]，可能需要dp[i+1][j-stones[i]]，需不需要dp[i+1][j-stones[i]]还要看stones[i] <= j是否成立，我疑惑的点在于相较于本文中dp[i][j]只依赖与dp数组中相邻的位置，而本题可能还牵扯到了除了dp数组外的其他数组，那么此时判断能否空间压缩仍然是看dp[i][j]是不是只依赖dp数组中的相邻位置，还是考虑时也要带上另一个stones数组呢？感觉这里不是很明白，希望东哥能指点一下
