对动态规划进行降维打击 :: labuladong的算法小抄

[labuladong]

文章链接点这里：对动态规划进行降维打击

评论礼仪 见这里，违者直接拉黑。

[xiangyueerli]

strong!

[shiboys]

妙不可言。最好是调试+对着图片，然后看看代码的具体走向和流程，就能明白 pre 的用法

[yunerss]

牛皮

[lzh2580]

一脸懵逼的看完了。。。for (int j = i + 1; j < n; j++) {这里跟j=i+1初始条件没有任何关系。外层循环第一行定义一个变量，内层循环最后一行对这个变量赋值，这个变量就是i+1，j-1的值。循环条件是i--，j++

[bert82503]

打卡，感谢！👍

[LebronHarden1]

好累

[LebronHarden1]

看懂啦!谢谢东哥的空间压缩~!
小而精的那块,就是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],所以就都考虑到了.就想在一维数组上一直对老值做修改形成一个滚动的效果

[lhcezx]

东哥，请问自顶向下的DP如何对备忘录进行空间压缩呢？

[labuladong]

@lhcezx 不好压缩，所以一般都是把自顶向下的递归解法改成自底向上的迭代算法，然后再压缩

[guqihao-7]

东哥你好，对于文中这一句如果计算状态 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数组呢？感觉这里不是很明白，希望东哥能指点一下

[Velliy]

pre为啥在for循环里面初始化呢？那这样不就和i-1没关系了么？

[SUN7700]

我也是有点不知道为什么在第一次循环里面init

[twotwoba]

因为 i 是控制每一层的呀

[SUN7700]

感觉这一节有点烧脑，看了很久才模模糊糊知道流程是怎么在走，看懂了流程，但感觉还是很懵😱😱😱

[yonggui-yan]

滴滴，打卡

[reborm]

一维看不太懂呀，我就掌握二维的算了

[labuladong]

可以的，一般题目不用空间压缩也能通过所有测试用例，毕竟时间复杂度都是一样的。

[GoingMyWay]

俄罗斯套娃信封问题也是空间压缩的一种吧？

[labuladong]

不是，那应该算是问题的抽象和转化

[SUN7700]

过了一个月回来看这篇文章，还是没弄懂空间压缩😭

[KScaesar]

我買書看到這章節也是不懂
後來找網路 看到這個 pdf
裡面有一些簡單的範例
先看簡單的, 可能比較好理解
可以參考看看

主要是 這個例子 投影到一維
有兩個元素互相重疊
才造成需要 有另一個變數暫存
變得好燒腦

[morganwu277]

谢谢提供资料，很好的连接。

[qylixin]

新d[j] 需要 旧d[j]+新d[j-1]以及旧d[j-1]计算出来
旧d[j]就是d[i+1][j]，即未被覆盖前的d[j]
新d[j-1]就是d[i][j-1]
这两个好理解
旧d[j-1]可以先不管，直接考虑d[j+1]怎么算

新d[j+1] 需要 旧d[j+1]+新d[j]以及旧的d[j]计算出来
旧的d[j]就是上一步在计算新d[j]的时候被覆盖掉的，而被覆盖的时机就是内层for循环更新j值的时候，所以就需要在内层for循环是记录旧的d[j]值

[bruceeewong]

打卡！降维的可读性真的好差2333，一刷先懂个大概！等二三刷来加强理解

[CarlLy7]

哎，没看懂

[shiboys]

我觉得楼主对 temp=pre 这行代码解释的不够好，下面是我的解释，个人认为比楼主的解释好
我对着图仔细的观察了下， 发现 内存 for 循环的第一行的 dp[j] 在更改之前代表的是二维数组中上一行 dp[i+1]j，然后被赋值给变量 temp，这是内循环第一行的逻辑。

然后在内层循环的最后一行，下一轮内层 j++ 循环之前，pre = temp; 这行代码
将这个数据存在 pre 变量上。
当下一个 j++ 循环开始后，此时的 pre 就从上一次的dp[i+1][j] 就变成了当前内层循环的 dp[i+1][j-1](因为 j++ 了嘛！长大后我就成了你)，这个非常难以发现。

[shiboys]

「dp[i+1]j 」应该是 「dp[i+1][j] 」不知道怎么格式错乱了

[shiboys]

dp[j] 代表了dp[i+1][j]，可以理解为接口调用中的透传，或者理解为从上一轮外层循环中顺带过来的

[kewen645]

是的，笔记上，楼主把这个最重要的转换忽略，用数字举例也没体现到这个temp = dp[j], 其实是对于外层for循环上一轮的dp[i + 1][j]

[lzh2580]

这是来自QQ邮箱的假期自动回复邮件。   您好，我最近正在休假中，无法亲自回复您的邮件。我将在假期结束后，尽快给您回复。