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];

    }
}

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