从前向后看？(考古回来啦！！！)

Question

https://coding.imooc.com/learn/questiondetail/jxkpVYBVAEjYrwRQ.html
关于这个问题中：从前往后看的的意思(不是从len-1开始)，我用代码列出来，老师看看对不对。

public class Package01 {

    /**
     * 暴力解法
     * 就是遍历所有的物品[0...n-1]  然后选与不选 遍历出所有可能 取出最大值
     */
    public static int package01(int[] weight, int[] value, int capacity) {
        return package01(weight, value, capacity, 0);
    }

    private static int package01(int[] weight, int[] value, int capacity, int start) {
        if (start >= weight.length)
            return 0;
        if (capacity <= 0)
            return 0;
        //选择当前物品
        int ans1 = 0;
        if (capacity >= weight[start])
            ans1 = package01(weight, value, capacity - weight[start], start + 1) + value[start];
        //不选择当前物品
        int ans2 = package01(weight, value, capacity, start + 1);
        return Math.max(ans1, ans2);
    }

    /**
     * 记忆化搜索
     * 定义二维数组 memo[i][j] 表示  在容量j的前提下 从[0..i]这些物品中选择出最大的价值为memo[i][j]
     */
    static int[][] memo;

    public static int package01RS(int[] weight, int[] value, int capacity) {
        memo = new int[weight.length + 1][capacity + 1];
        return package01RS(weight, value, capacity, 0);
    }

    public static int package01RS(int[] weight, int[] value, int capacity, int start) {
        if (start >= weight.length)
            return 0;
        if (capacity <= 0)
            return 0;
        if (memo[start][capacity] != 0)
            return memo[start][capacity];
        //选择当前物品
        int ans1 = 0;
        if (capacity >= weight[start])
            ans1 = package01(weight, value, capacity - weight[start], start + 1) + value[start];
        //不选择当前物品
        int ans2 = package01(weight, value, capacity, start + 1);
        memo[start][capacity] = Math.max(ans1, ans2);
        return memo[start][capacity];
    }

    public static int package0DP(int[] weight, int[] value, int capacity) {
        int[][] dp = new int[weight.length][capacity + 1];
        for (int i = 0; i < weight.length; i++) {
            dp[i][0] = 0;
        }
        for (int i = 0; i < capacity + 1; i++) {
            if (i >= weight[0])
                dp[0][i] = value[0];
        }
        for (int i = 1; i < weight.length; i++) {
            for (int j = 1; j < capacity + 1; j++) {
                if (j >= weight[i])
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }

        return dp[weight.length - 1][capacity];
    }

    public static void main(String[] args) {
        int[] w = {6, 1, 5, 2, 1};
        int[] v = {48, 7, 40, 12, 8};
        System.out.println(package0DP(w, v, 8));
    }
}

暴力解法和记忆化搜索就是从前完后看，从[0…len-1]物品中，查找C得最大值。思路就是从头开始遍历。0不选->[1…len-1] 最大值，和选0->[1…len-1的最大值+v[0]。老师看对吗？

问题2：
关于动态规划相关的问题。我的理解就是当使用记忆化搜索方式去解决问题时，是用的正向思维。正向思维是自顶向下，从最开始的小问题，依次解决，最终解决原问题。逆向思维，自底向上，从最终的过程(是过程不是结果)往开始推导。所以是逆向思维。
举个例子，LeetCode 198 打家劫舍 用记忆化搜索，很多题解都是将最后一间房，要么打劫，要么不打劫。来去推到动态转移方程。这种方式肯定是对的，但不好理解(对于我这种小白)，其实记忆化搜索，和之前的所有递归解决的问题思想一致，就是先解决一个小的问题，然后不断递归解决更大的问题，直到解决最终问题。

那么打家劫舍-记忆化搜索的思想就应该是，偷1 个。(记作i也可以)间房子和不偷第1 个 (记作i也可以)间房子，求max，然后一直递归到最后一间房子。这就是我所说的：正向-自顶向下去思考。
在理解了记忆化搜索的正向思考后，在自底向上去思考。如果我从最后一间房子去思考。去偷最后一间，和不去偷最后一间，求max。这样层层向上，用控制循环和dp来进行回溯。所以如果想用记忆化搜索，用从前向后看更好理解。比如下面我的代码

/**
 * hint 动态规划问题再求解时  复习的时候都要去写状态定义 和状态转移方程
 *
 * @author zg
 * @date 2023/8/17 14:44
 * <p>
 * 198. 打家劫舍
 * 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，
 * 影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
 * <p>
 * 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
 * <p>
 * https://leetcode.cn/problems/house-robber/solutions/424065/wo-shi-yi-ge-hui-dong-tai-gui-hua-de-xiao-tou-by-b/
 */
public class Solution198Repeat {
    /**
     * 记忆化搜索
     * 正向思维思考
     * [2 7 9 3 1]
     * 将原问题转化成更小的问题 ：求[i....n] 中打劫的最大数 转化为num[i]+rob[i+2...n]，
     * 即 选取偷i间屋子 再求 偷[i+2...n]之前最大的金额 相加 依次递归
     */
    int[] memo;

    public int rob(int[] nums) {
        int len = nums.length;
        if (len == 1)
            return nums[0];
        if (len == 2)
            return Math.max(nums[0], nums[1]);

        memo = new int[len + 1];
        Arrays.fill(nums, -1);
        return robRS(nums, 0, len);
    }

    private int robRS(int[] nums, int start, int end) {
        if (start >= end)
            return 0;

        if (memo[start] != -1)
            return memo[start];
        for (int i = start; i < end; i++) {
            memo[start] = Math.max(nums[i] + robRS(nums, i + 2, end), memo[start]);
        }

        return memo[start];
    }


    /**
     * 记忆化搜索是正向思维 自顶向下的递归
     * 动态规划是自底向上  所以是从右向左
     * <p>
     * 自底向上思考我们就要分情况分析 H代表第几间房子  H1第一件房子 对应nums[0]
     * <p>
     * 当只有1间房子  能投的选择只有1个 即 f(1)=H1
     * 当只有2间房子  能投的选择两个中最大的一个 即 f(2)=max(H1,H2)
     * 当有3间房子
     * 选择偷最后一个 则 f(3)=f(3-2)+ H3
     * 不选择偷最后一个 则 f(3)=f(2)
     * 当 4间房子
     * 选择偷最后一个 则 f(4)=f(4-2)+H4
     * 不选择偷最后一个 则 f(4)=f(3)
     * 当 n间房子
     * 选择偷最后一个 则 f(n)=f(n-2)+Hn
     * 不选择偷最后一个 则 f(n)=f(n-1)
     * 所以动态转移方程为 n>3 f(n)=max(f(n-1),f(n-2)+Hn)
     */
    public int robDP(int[] nums) {
        int len = nums.length;
        if (len == 1)
            return nums[0];
        if (len == 2)
            return Math.max(nums[0], nums[1]);
        int[] dp = new int[len + 1];
        dp[1] = nums[0];//偷
        dp[2] = Math.max(nums[0], nums[1]);

        for (int i = 3; i < len; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }

        return dp[len - 1];

    }
}

老师，最后想请问下：我这样的思想，这么理解对吗？

Answer 1

liuyubobobo 2023-08-21 16:20:01

我没有测试你的代码，整体看了一遍你的思路，大体理解是没有问题的。

几个细节，我再“细扣”一下，看一下你是否理解。（如果不理解也没有关系，你提问的两个问题的代码如果都可以 ac 的话，并且这两个代码都是你自己写出来的话，对于这两个问题，你的理解已经没有问题了。）

==========

对于你的第一个问题：

其实我不很确定你说的“从前向后和从后向前”到底是如何定义的，但是我根据字面的理解，“从前向后和从后向前”与“自顶向下和自底向上”是两个概念。

我们在学习记忆化搜索和动态规划的时候，强调的是“自顶向下和自底向上”这个概念。记忆化搜索是自顶向下的，动态规划是自底向上的。

因为记忆化搜索的过程是：为了求解一个更大的问题，递归地去处理更小的问题。（自顶向下）

在你的代码中，即为了求解 package01RS(capacity, start) 这个问题，我们递归地去求解 package01RS(capacity, start + 1) 和 package01RS(capacity - weight[start], start + 1)。

package01RS(capacity, start + 1) 和 package01RS(capacity - weight[start], start + 1) 比 package01RS(capacity, start) 更小，想一想是为什么？？？

而动态规划的过程是，求出了更小的问题以后，进一步求更大的问题。（自底向上）

在你的代码中，即先算出了 dp[i - 1][j] 和 dp[i - 1][j - weight[i]]，再求的 dp[i][j]。

dp[i - 1][j] 和 dp[i - 1][j - weight[i]] 比 dp[i][j] 小，想一想为什么？

而“从前向后和从后向前”我从字面上理解，只是对于一个一维数组，是从第一个元素开始看，还是从最后一个元素开始看而已。

对于背包问题，我们可以从第一个物品开始看，直到看到第 n - 1 个物品；也可以从第 n - 1 个物品开始看，直到看到第 0 物品；

同理，打家劫舍，也可以从第一个房间开始看，直到看到最后一个房间，或者反之，从最后一个房间开始看，最后看到第一个房间。

也正因此，“从前向后和从后向前”不是动态规划或者记忆化搜索“学习”的重点，因为这个方向无所谓。（就像遍历一个数组，从前向后遍历或者从后向前遍历，都能遍历完所有的元素。）

但既然你提到这里，你问题中的这两个问题，都能写出 4 个解法：

1）记忆化搜索（自顶向下），从前向后看物品；

2）记忆化搜索（自顶向下），从后向前看物品；

3）动态规划（自底向上），从前向后看物品；

4）动态规划（自底向上），从后向前看物品；

（打家劫舍中，“房间”即“物品”）

感兴趣可以把这两个问题的四个解法都写一遍，再对比一下，加深一下理解；

==========

对于你的第二个问题：

我不确定我是不是理解了你的问题，但是整体，自顶向下是比自底向上容易想的；即记忆化搜索比动态规划的思维难度低。如果你有这个感觉，就对了。

之前有同学有类似的问题，感兴趣可以看看这个问答：https://coding.imooc.com/learn/questiondetail/y82Qv6AKpa2Yd5Nn.html

这个问题就是典型的，写记忆化搜索远比写动态规划容易。

（另外，这个问题使用了状态压缩，我个人不认为状态压缩式面试必备的知识，所以这个问题你不会做也没有关系，我只是让你感兴趣的话看一下我描述的记忆化搜索和动态规划之间的关系，以及为什么记忆化搜索比动态规划简单。）

继续加油！：）

• 提问者 慕妹2978617 #1

  是我思维有些局限了，其实从前往后，或是从后往前，是我定义对象从哪里开始取，比如0-1背包问题，我理解的从前往后其实更像是[0..n-1]取遍历，反之[n-1...0],但这并不是动态规划类型题目的核心，核心应该是回溯类问题通常是树形结构问题，自定向下是从根节点思考问题，直到树的尾节点(满足题意，或不满足题意返回，当返回的结果这一层，就是基本问题，根节点是个大问题)解决后记录最后路线，然后根据返回判断是否是最优解。通过回溯的过程，将结果一致回退(或者叫推导)原问题(最开始的问题)这才是自顶向下， 而自底向上，就把最基本的问题解决，一直扩大，直到扩大的范围到原问题给的范围，返回解。所以自顶向下或自底向上，都是针对树形问题，看你是从最大问题入手，还是从最小问题不断扩大推导出最大问题(所求问题)。和遍历问题条件(数组或数字)从大到小，或左到右是没关系的。这样理解对吗？

• liuyubobobo 回复 提问者 慕妹2978617 #2

  大赞！用树结构去理解非常非常非常对！自顶向下就是从根到叶；自底向上就是从叶到根。再赞一下！：）