动态规划

确定dp数组（dp table）以及下标的含义

确定递推公式

dp数组如何初始化

确定遍历顺序

举例推导dp数组

• 返回结果是看遍历顺序如何推倒的

爬楼梯 - LeetCode 70

• 定义dp数组：dp[i]表示爬到第i级台阶的方法数
• 递推公式：dp[i] = dp[i-1] + dp[i-2]，因为爬到第i级台阶的方法数等于爬到第i-1级台阶的方法数加上爬到第i-2级台阶的方法数
• 初始化：dp[0] = 1，dp[1] = 1，因为爬到第0级台阶的方法数是1，爬到第1级台阶的方法数是1
• 遍历顺序：从2到n，因为爬到第0级台阶的方法数是1，爬到第1级台阶的方法数是1
• 返回结果：dp[n]

public int climbStairs(int n) {
    int[] dp = new int[n + 1]; // 数组下标从 0 开始，所以要能存到 dp[n]，数组长度至少为 n + 1。
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

使用最小花费爬楼梯 - LeetCode 746

• 定义dp数组：dp[i]表示爬到第i级台阶的最小花费
• 递推公式：dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])，因为爬到第i级台阶的最小花费等于爬到第i-1级台阶的最小花费加上第i-1级台阶的花费和爬到第i-2级台阶的最小花费加上第i-2级台阶的花费中的最小值
• 初始化：dp[0] = 0，dp[1] = 0，因为爬到第0级台阶的最小花费是0，爬到第1级台阶的最小花费是0，因为题目中说可以从第0级台阶或者第1级台阶开始爬楼梯，只有跳的时候才需要开始花费
• 遍历顺序：从2到n，因为爬到第0级台阶的最小花费是0，爬到第1级台阶的最小花费是0
• 返回结果：dp[n]

public int minCostClimbingStairs(int[] cost) {
    int[] dp = new int[cost.length + 1];
    dp[0] = 0;
    dp[1] = 0; 
    for (int i = 2; i <= cost.length; i++) {
        dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
    }
    return dp[cost.length];
}

不同路径 - LeetCode 62

• 定义dp数组：dp[i][j]表示从左上角到(i, j)的路径数
• 递推公式：dp[i][j] = dp[i-1][j] + dp[i][j-1]，因为从左上角到(i, j)的路径数等于从左上角到(i-1, j)的路径数加上从左上角到(i, j-1)的路径数
• 初始化：dp[i][0] = 1，dp[0][j] = 1，因为从左上角到(i, 0)的路径数是1，从左上角到(0, j)的路径数是1
• 遍历顺序：从1到m，从1到n
• 返回结果：dp[m-1][n-1]

public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    for (int i = 0; i < m; i++) {
        dp[i][0] = 1;
    }
    for (int j = 0; j < n; j++) {
        dp[0][j] = 1;
    }
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[m-1][n-1];
}

不同路径II - LeetCode 63

• 障碍物：obstacleGrid[i][j] = 1
• 定义dp数组：dp[i][j]表示从左上角到(i, j)的路径数
• 递推公式：如果obstacleGrid[i][j]为0，则dp[i][j] = dp[i-1][j] + dp[i][j-1]，因为从左上角到(i, j)的路径数等于从左上角到(i-1, j)的路径数加上从左上角到(i, j-1)的路径数
• 初始化：如果obstacleGrid[i][0]为0，则dp[i][0] = 1，否则为0；如果obstacleGrid[0][j]为0，则dp[0][j] = 1，否则为0
• 遍历顺序：从1到m，从1到n
• 返回结果：dp[m-1][n-1]

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    int m = obstacleGrid.length;
    int n = obstacleGrid[0].length;
    int[][] dp = new int[m][n];
    
    // 初始化第一列
    for (int i = 0; i < m; i++) {
        if (obstacleGrid[i][0] == 1) {
            dp[i][0] = 0; // 有障碍后面的都无法走到
            break;
        } else {
            dp[i][0] = 1;
        }
    }
    
    // 初始化第一行
    for (int j = 0; j < n; j++) {
        if (obstacleGrid[0][j] == 1) {
            dp[0][j] = 0;
            break;
        } else {
            dp[0][j] = 1;
        }
    }
    
    // 填充dp数组
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (obstacleGrid[i][j] == 1) {
                dp[i][j] = 0;
            } else {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
    }
    
    return dp[m - 1][n - 1];
}

整数拆分 - LeetCode 343

• 定义dp数组：dp[i]表示拆分整数i的最大乘积
• 递推公式：dp[i] = max(dp[i], j * (i - j), j * dp[i - j])，因为拆分整数i的最大乘积等于拆分整数i-j的最大乘积乘以j，或者拆分整数i-j的最大乘积乘以j，或者拆分整数i-j的最大乘积乘以j
• 初始化：dp[0] = 0，dp[1] = 0，因为拆分整数0的最大乘积是0，拆分整数1的最大乘积是0
• 遍历顺序：从2到n，因为拆分整数2的最大乘积是1，拆分整数3的最大乘积是2
• 返回结果：dp[n]

public int integerBreak(int n) {
    int[] dp = new int[n + 1];
    dp[2] = 1;
    for (int i = 3; i <= n; i++) {
        for (int j = 1; j < i - 1; j++) {
            dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
        }
    }
    return dp[n];
}

背包问题

背包类型	问题类型	推荐数组类型	遍历顺序	是否倒序容量	状态转移方程
01背包	价值最大	一维 / 二维	先物品，再容量	✅（一维需要）❌（二维不需要）	dp[j] = max(dp[j], dp[j-w] + v)
完全背包	价值最大	一维 / 二维	先物品，再容量（正序）	❌	dp[j] = max(dp[j], dp[j-w] + v)
完全背包	组合数	一维 / 二维	先物品，再容量（正序）	❌	dp[j] += dp[j-w]
完全背包	排列数	一维	先容量，再物品（正序）	❌	dp[j] += dp[j-w]

                            |

• ✅ 01背包一维数组要倒序，防止同一轮多次选同一个物品。
• ❌ 二维数组不需要倒序，因为每层是独立的，不会重复使用。
• ✅ 完全背包组合数是"先物品再容量"，保证每种组合只计算一次。
• ✅ 完全背包排列数是"先容量再物品"，考虑顺序不同的情况。

01背包

• 问：在 01 背包中，为什么状态转移依赖的是 dp[i-1][j] 而不是 dp[i][j]？

  • 因为每个物品只能选一次。如果使用 dp[i][j] 来转移，会导致你在当前层中重复使用同一个物品，这就变成了 完全背包（物品可以无限用）。

• 二维数组

• dp数组含义：dp[i][j]表示前i个物品在容量为j时的最大价值

• 递推公式：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)，因为第i个物品可以装也可以不装

• 初始化：dp[0][j] = 0，因为前0个物品在容量为j时的最大价值是0

• 遍历顺序：从1到n，从0到capacity，顺序可以颠倒，因为当前值是依赖上一行和左上方的值，不会出现没有初始化的情况

• 返回结果：dp[n][capacity]

public static int knapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[][] dp = new int[n + 1][capacity + 1];
    // dp[i][j]：前 i 件物品在容量为 j 时的最大价值
    for (int i = 1; i <= n; i++) { // 遍历物品
        int w = weights[i - 1];
        int v = values[i - 1];
        for (int j = 0; j <= capacity; j++) { // 遍历背包容量
            if (j < w) {
                dp[i][j] = dp[i - 1][j];  // 装不下
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w] + v);  // 装 or 不装
            }
        }
    }
    return dp[n][capacity];
}

• 一维数组，因为第 i 行只用到第 i-1 行的数据，所以可以优化空间复杂度，从二维数组优化到一维数组。
• dp数组含义：dp[j]表示容量为j时的最大价值
• 递推公式：dp[j] = max(dp[j], dp[j-w] + v)，因为第i个物品可以装也可以不装
• 初始化：dp[0] = 0，因为前0个物品在容量为j时的最大价值是0
• 遍历顺序：遍历背包的时候倒序遍历，因为要防止重复选同一个物品。顺序不可以颠倒，因为如果颠倒顺序的话也会重复选取同一个物品 就会变成完全背包。
• 返回结果：dp[capacity]

public static int knapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[] dp = new int[capacity + 1];
    for (int i = 0; i < n; i++) {
        for (int j = capacity; j >= weights[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}

完全背包

public static int knapsackComplete(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[] dp = new int[capacity + 1];
    for (int i = 0; i < n; i++) { // 遍历物品
        for (int j = weights[i]; j <= capacity; j++) { // 正序遍历背包容量
            dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}

分割等和子集 - LeetCode 416

• dp数组含义：dp[j]表示容量为j时的最大价值
• 递推公式：dp[j] = max(dp[j], dp[j-nums[i]] + nums[i])，本题中背包容量和物品价值是一个东西，所以dp[j] = max(dp[j], dp[j-nums[i]] + nums[i])
• 初始化：dp[0] = 0，因为前0个物品在容量为j时的最大价值是0，dp[j] = 0 因为递推公式取的是max 所以要取非负数的最小值这样不会破坏递推结果
• 遍历顺序：先物品再背包 背包倒序遍历
• 返回结果：dp[capacity] == capacity 如果dp[capacity] == capacity 说明可以分割成两个等和子集

public boolean canPartition(int[] nums) {
    int sum = 0; // 计算总和
    for (int num : nums) {
        sum += num;
    }
    if (sum % 2 != 0) return false; // 如果总和是奇数，则不能分割成两个等和子集
    int target = sum / 2; // 计算目标值
    int[] dp = new int[target + 1]; // 初始化dp数组全部为0
    for (int i = 0; i < nums.length; i++) { // 遍历物品
        for (int j = target; j >= nums[i]; j--) { // 遍历背包
            dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]); // 状态转移方程
        }
    }
    return dp[target] == target; // 如果dp[target] == target 说明可以分割成两个等和子集
}

最后一块石头的重量II - LeetCode 1049

• 思路：将石头分成两堆，使得两堆石头的重量尽可能接近，最后一块石头的重量就是两堆石头重量的差值。
• dp数组含义：dp[j]表示容量为j时的最大价值
• 递推公式：dp[j] = max(dp[j], dp[j-stones[i]] + stones[i])，本题中背包容量和物品价值是一个东西，所以dp[j] = max(dp[j], dp[j-stones[i]] + stones[i])
• 初始化：dp[0] = 0，因为前0个物品在容量为j时的最大价值是0，dp[j] = 0 因为递推公式取的是max 所以要取非负数的最小值这样不会破坏递推结果
• 遍历顺序：先物品再背包 背包倒序遍历
• 返回结果：sum - 2 * dp[target] 因为dp[target]是两堆石头中较重的一堆，所以最后一块石头的重量就是两堆石头重量的差值

public int lastStoneWeightII(int[] stones) {
    int sum = 0; // 计算总和
    for (int stone : stones) {
        sum += stone; // 计算总和
    }
    int target = sum / 2; // 计算目标值，因为要使得两堆石头重量尽可能接近，所以目标值是总和的一半
    int[] dp = new int[target + 1]; // 初始化dp数组全部为0
    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]; // 返回结果
}

目标和 - LeetCode 494

• 思路：将数组分成两部分，一部分为正数，一部分为负数，使得正数和负数之和等于target。
• dp数组含义：表示容量为j的时候有dp[j]种方法可以装满
• 递推公式：dp[j] += dp[j-nums[i]] 因为dp[j]可以由dp[j-nums[i]]推导出来
• 初始化：dp[0] = 1，因为容量为0的时候只有一种方法可以装满
• 遍历顺序：先物品再背包 背包倒序遍历
• 返回结果：dp[bagSize]
  • bagSize = (target + sum) / 2 因为
  • 推导过程：

P: 正数和
N: 负数和

P + N = sum
P - N = target
----------------
2P = sum + target
P = (sum + target) / 2

public int findTargetSumWays(int[] nums, int target) {
    int sum = 0;
    for (int i = 0; i < nums.length; i++) sum += nums[i]; // 计算数组总和
    //如果target的绝对值大于sum，那么是没有方案的
    if (Math.abs(target) > sum) return 0;
    //如果(target+sum)除以2的余数不为0，也是没有方案的
    if ((target + sum) % 2 == 1) return 0;
    int bagSize = (target + sum) / 2; // 计算背包容量
    int[] dp = new int[bagSize + 1]; // 初始化dp数组
    dp[0] = 1; // 初始化dp[0] = 1 
    for (int i = 0; i < nums.length; i++) {
        for (int j = bagSize; j >= nums[i]; j--) {
            dp[j] += dp[j - nums[i]];
        }
    }
    return dp[bagSize];
}

买卖股票问题

买卖股票的最佳时机1 - LeetCode 121

• 一只股票只能买卖一次
• 定义dp数组：dp[i][0]表示第i天不持有股票的最大利润，dp[i][1]表示第i天持有股票的最大利润
• 递推公式：dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])，dp[i][1] = max(dp[i-1][1], -prices[i])
• 初始化：dp[0][0] = 0，dp[0][1] = -prices[0]
• 遍历顺序：从1到n，从0到1
• 返回结果：dp[n][0]

public int maxProfit(int[] prices) {
    int[][] dp = new int[prices.length][2];
    dp[0][0] = 0; // 第0天不持有股票的最大利润
    dp[0][1] = -prices[0]; // 第0天持有股票的最大利润
    for (int i = 1; i < prices.length; i++) {
        dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]); // 第i天不持有股票的最大利润 要么是前一天不持有股票的最大利润 要么是前一天持有股票的最大利润加上今天卖出股票的利润
        dp[i][1] = Math.max(dp[i-1][1], -prices[i]); // 第i天持有股票的最大利润 要么是前一天持有股票的最大利润 要么是今天买入股票的利润
    }
    return dp[prices.length-1][0]; // 返回最后一天不持有股票的最大利润 因为最后一天不持有股票的利润一定比持有股票的利润高
}

买卖股票的最佳时机2 - LeetCode 122

• 一只股票可以买卖多次 所以在今天买入股票的时候 需要从昨天的不持有股票的最大利润中减去今天的股票价格
• 定义dp数组：dp[i][0]表示第i天不持有股票的最大利润，dp[i][1]表示第i天持有股票的最大利润
• 递推公式：dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])，dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
• 初始化：dp[0][0] = 0，dp[0][1] = -prices[0]
• 遍历顺序：从1到n，从0到1
• 返回结果：dp[n][0]

public int maxProfit(int[] prices) {
    int[][] dp = new int[prices.length][2];
    dp[0][0] = 0; // 第0天不持有股票的最大利润
    dp[0][1] = -prices[0]; // 第0天持有股票的最大利润
    for (int i = 1; i < prices.length; i++) {
        dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]); // 第i天不持有股票的最大利润 要么是前一天不持有股票的最大利润 要么是前一天持有股票的最大利润加上今天卖出股票的利润
        dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]); // 第i天持有股票的最大利润 要么是前一天持有股票的最大利润 要么是前一天不持有股票的最大利润加上今天买入股票的利润
    }
    return dp[prices.length-1][0]; // 返回最后一天不持有股票的最大利润 因为最后一天不持有股票的利润一定比持有股票的利润高
}

买卖股票的最佳时机3 - LeetCode 123

• 一只股票最多可以买卖两次

public int maxProfit(int[] prices) {
    int len = prices.length;
    // 边界判断, 题目中 length >= 1, 所以可省去
    if (len == 0) return 0;
    /*
     * 定义 5 种状态:
     * 0: 没有操作, 1: 第一次买入, 2: 第一次卖出, 3: 第二次买入, 4: 第二次卖出
     */
    int[][] dp = new int[len][5];
    dp[0][1] = -prices[0];
    // 初始化第二次买入的状态是确保 最后结果是最多两次买卖的最大利润
    dp[0][3] = -prices[0];
    for (int i = 1; i < len; i++) {
        dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
        dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
        dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
        dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
    }
    return dp[len - 1][4]; // 为了使收益最大，最终选择「最多两次交易」的最大利润，也就是状态 4（第二次卖出）所对应的最大值。
}

买卖股票的最佳时机4 - LeetCode 188

• 一只股票最多可以买卖k次 其实就是买卖股票的最佳时机3的扩展 只不过把2次交易变成了k次交易 要找到一个公式

public int maxProfit(int k, int[] prices) {
    if (prices.length == 0) return 0;
    // [天数][股票状态]
    // 股票状态: 奇数表示第 k 次交易持有/买入, 偶数表示第 k 次交易不持有/卖出, 0 表示没有操作
    int len = prices.length;
    int[][] dp = new int[len][k*2 + 1]; // 2*k+1是因为有k次交易，每次交易有2个状态，持有和卖出
    
    // dp数组的初始化，把偶数位置初始化为0，奇数位置初始化为-prices[0]
    for (int i = 1; i < k*2; i += 2) { // 奇数表示第 k 次交易持有/买入, 偶数表示第 k 次交易不持有/卖出, 0 表示没有操作 i+=2是因为奇数和偶数是交替出现的
        dp[0][i] = -prices[0];
    }
    for (int i = 1; i < len; i++) {
        for (int j = 0; j < k*2 - 1; j += 2) {
            dp[i][j + 1] = Math.max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]); // j+1表示第k次交易持有/买入
            dp[i][j + 2] = Math.max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]); // j+2表示第k次交易不持有/卖出
        }
    }
    return dp[len - 1][k*2]; // 返回最后一天第k次交易不持有/卖出的最大利润
}

买卖股票的最佳时机含冷冻期 - LeetCode 309

• 卖出股票后，第二天不能买入股票

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if(n == 0) return 0;
        int[][] dp = new int[n][3];
        dp[0][0] = 0;           // 未持股，非冷冻期
        dp[0][1] = -prices[0];  // 持股
        dp[0][2] = 0;           // 冷冻期

        for(int i = 1; i < n; i++){
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][2]);
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);
            dp[i][2] = dp[i-1][1] + prices[i];
        }
        return Math.max(dp[n-1][0], dp[n-1][2]);
    }
}

买卖股票的最佳时机含手续费 - LeetCode 714

• 每次交易需要支付手续费 在卖出股票的时候需要减去手续费

public int maxProfit(int[] prices, int fee) {
    int n = prices.length;
    int[][] dp = new int[n][2];
    dp[0][0] = 0;
    dp[0][1] = -prices[0];
    for (int i = 1; i < n; i++) {
        dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i] - fee);
        dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);
    }
    return dp[n-1][0];
}

子序列问题

最长递增子序列 - LeetCode 300

• 定义dp数组：dp[i]是以nums[i]为结尾的最长递增子序列的长度
• 递推公式（状态转移方程）：如果nums[i]>nums[j]，dp[i]=max(dp[j]+1,dp[i])，要想到dp[i]由哪些状态可以推出来，并取最大值
• 初始化：dp[i]=1，至少长度都包含nums[i]，一个元素结尾 长度就是1
• 遍历顺序：从小到大遍历，因为推出后面的元素需要依赖前面的元素结果

for (int i = 1; i < dp.length; i++) { // i从1开始 因为dp[0]肯定是1
        for (int j = 0; j < i; j++) { // j其实就是遍历0到i-1 比较i前的所有元素（用j遍历的）
            // 递推公式
        }
    res = Math.max(res, dp[i]); // 存入结果，注意结果不是dp[nums.size-1]
}

• 打印dp检查

public int lengthOfLIS(int[] nums) {
    if (nums.length <= 1) return nums.length;
    int[] dp = new int[nums.length];
    int res = 1;
    Arrays.fill(dp, 1); // dp[i] = 1
    for (int i = 1; i < dp.length; i++) {
        for (int j = 0; j < i; j++) { // 遍历0-i的所有元素 比较i和j的大小
            if (nums[i] > nums[j]) { // 
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        res = Math.max(res, dp[i]); // 取每一次遍历的最大值
    }
    return res;
}

最长连续递增子序列 - LeetCode 674

• 定义dp数组：dp[i]是以nums[i]为结尾的最长连续递增子序列的长度
• 递推公式（状态转移方程）：只比较i和i-1的位置，不需要像上一题比较i前的所有元素（用j遍历的）。如果nums[i]>nums[i-1]，dp[i]=dp[i-1]+1
• 初始化：dp[i]=1，至少长度都包含nums[i]，一个元素结尾 长度就是1
• 遍历顺序：从小到大遍历，因为推出后面的元素需要依赖前面的元素结果

for (int i = 1; i < dp.length; i++) { // i从1开始 因为dp[0]肯定是1
    // 递推公式
    res = Math.max(res, dp[i]); // 存入结果，注意结果不是dp[nums.size-1]
}

• 打印dp检查

public static int findLengthOfLCIS(int[] nums) {
    int[] dp = new int[nums.length];
    Arrays.fill(dp, 1);
    int res = 1;
    for (int i = 1; i < nums.length - 1; i++) {
        if (nums[i + 1] > nums[i]) {
            dp[i + 1] = dp[i] + 1;
        }
        res = res > dp[i + 1] ? res : dp[i + 1];
    }
    return res;
}
// 优化：不需要dp数组，直接用count计数，遇到更大的就count++，遇到更小的就count=1（贪心）
public static int findLengthOfLCIS(int[] nums) {
    if (nums.length == 0) return 0;
    int count = 1, res = 1;
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] > nums[i - 1]) {
            count++;
        } else {
            count = 1; // 重新开始
        }
        res = Math.max(res, count);
    }
    return res;
}

最长重复子数组（元素要求连续） - LeetCode 718

• 定义dp数组：以下标i - 1为结尾的nums1，和以下标j - 1为结尾的nums2，最长重复子数组长度为dp[i][j]。这样做简便初始化，不然如果以i和j结尾，又要循环遍历看有没有相等的第一个元素，要对第一行和第一列进行初始化，如果有还得初始化为1。但是现在就可以直接初始化为0
• 递推公式（状态转移方程）：根据dp[i][j]的定义，dp[i][j]的状态只能由dp[i - 1][j - 1](也就是左上角)推导出来。即当nums1[i - 1] 和nums2[j - 1]相等的时候，dp[i][j] = dp[i - 1][j - 1] + 1
• 初始化：dp[i][0] 和dp[0][j]初始化为0，因为求最长是从0开始加。其他地方初始化多少无所谓会被覆盖
• 遍历顺序：外层for循环遍历nums1，内层for循环遍历nums2，反过来也可以没区别

for (int i = 1; i <= nums1.size(); i++) { //从1开始因为`dp[i][0]` 和`dp[0][j]`初始化为0，而且实际上根据dp定义这俩没有意义
    for (int j = 1; j <= nums2.size(); j++) { // <=nums.size是因为dp数组的定义
        // 递推公式
        if (dp[i][j] > result) result = dp[i][j]; //遍历二维数组，找出最长重复子数组，结果并不是dp[nums1.size][nums2.size]
    }
}

• 打印dp检查

public int findLength(int[] nums1, int[] nums2) {
    int result = 0;
    int[][] dp = new int[nums1.length + 1][nums2.length + 1];
    
    for (int i = 1; i <= nums1.length; i++) {
        for (int j = 1; j <= nums2.length; j++) {
            if (nums1[i - 1] == nums2[j - 1]) {  // 因为 dp 的行和列从 1 开始（为了处理边界初始化方便），而数组 nums1 和 nums2 的下标是从 0 开始 的。所以 dp[i][j] 对应的是 nums1[i - 1] 和 nums2[j - 1]。
                dp[i][j] = dp[i - 1][j - 1] + 1;
                result = Math.max(result, dp[i][j]);
            }
        }
    }
    
    return result;
}

最长公共子序列（元素可以不连续，顺序保证即可） - LeetCode 1143

• 定义dp数组：长度为[0, i - 1]的字符串nums1与长度为[0, j - 1]的字符串nums2的最长公共子序列为dp[i][j]，这样做简便初始化，不然如果以i和j结尾，又要循环遍历看有没有相等的第一个元素，要对第一行和第一列进行初始化
• 递推公式（状态转移方程）：如果nums1[i - 1] 与 nums2[j - 1]相同，那么找到了一个公共元素，所以dp[i][j] = dp[i - 1][j - 1] + 1; 如果nums1[i - 1] 与 nums2[j - 1]不相同，那就看看nums1[0, i - 2]与nums2[0, j - 1]的最长公共子序列 和 nums1[0, i - 1]与nums2[0, j - 2]的最长公共子序列，取最大的。

if (nums1[i - 1] == nums2[j - 1]) {
    dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}

• 初始化：第一行和第一列，nums1[0, i-1]和空串的最长公共子序列自然是0，所以dp[i][0] = 0; 同理dp[0][j]也是0。所以第一行第一列都是0。其他地方初始化多少无所谓会被覆盖
• 遍历顺序：从坐向右，从上到下

for (int i = 1; i <= nums1.size(); i++) {
            for (int j = 1; j <= nums2.size(); j++) {
                // 递推公式
            }
}
return dp[text1.size()][text2.size()] // 结果

• 打印dp检查

public int longestCommonSubsequence(String text1, String text2) {
    char[] char1 = text1.toCharArray();
    char[] char2 = text2.toCharArray();

    int[][] dp = new int[text1.length() + 1][text2.length() + 1]; // 先对dp数组做初始化操作 
    for (int i = 1 ; i <= text1.length() ; i++) {
        for (int j = 1; j <= text2.length(); j++) {
            if (char1[i-1] == char2[j-1]) { // 开始列出状态转移方程
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // 不相同就取最大值
            }
        }
    }
    return dp[text1.length()][text2.length()];
}

不相交的线 - LeetCode 1035

• 其实就是找两个数组的最长公共子序列
• 公共子序列他们的线不会相交

最大子数组和（连续的和） - LeetCode 53

• 定义dp数组：包括下标i（以nums[i]为结尾）的最大连续子序列和为dp[i]
• 递推公式（状态转移方程）：dp[i]只有两个方向可以推出来：dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和，或者nums[i]，即：从头开始计算当前连续子序列和。dp[i] = max(dp[i - 1] + nums[i], nums[i])
• 初始化：从递推公式可以看出来dp[i]是依赖于dp[i - 1]的状态，dp[0]就是递推公式的基础。dp[0] = nums[0]
• 遍历顺序：递推公式中dp[i]依赖于dp[i - 1]的状态，需要从前向后遍历。

int result = dp[0];
for (int i = 1; i < nums.size(); i++) {
    // 递推公式
    if (dp[i] > result) result = dp[i]; // result 保存dp[i]的最大值
}

• 打印dp检查

// Kadane 算法 最大子数组和
public int maxSubArray(int[] nums) {
    int pre = 0, maxAns = nums[0]; // pre 是前一个元素的和，maxAns 是最大子数组和
    for (int x : nums) { // 遍历数组
        pre = Math.max(pre + x, x); // 如果前一个元素的和加上当前元素的值大于当前元素的值，则更新前一个元素的和 否则就只取当前元素的值
        maxAns = Math.max(maxAns, pre); // 如果当前元素的值大于前一个元素的和，则更新最大子数组和
    }
    return maxAns;
}

最大环形子数组和 - LeetCode 918

• 有两个选择 选最大的：
  • 不跨头尾（普通最大子数组和）：直接用 Kadane 算法求 maxSum
  • 跨头尾（环形情况）：total - minSum，也就是「总和减去中间最小的一段」

public int maxSubarraySumCircular(int[] nums) {
    int total = 0; // 总和
    int maxSum = nums[0], curMax = 0; // 最大子数组和 
    int minSum = nums[0], curMin = 0; // 最小子数组和

    for (int num : nums) {
        curMax = Math.max(curMax + num, num);
        maxSum = Math.max(maxSum, curMax); // 最大子数组和
        curMin = Math.min(curMin + num, num);
        minSum = Math.min(minSum, curMin); // 最小子数组和

        total += num; // 总和
    }

    // 如果 maxSum 全为负数，说明 total == minSum，不能环形，直接返回 maxSum 
    if (maxSum < 0) return maxSum;
    return Math.max(maxSum, total - minSum); // total - minSum 最大子数组是环形（跨两端）
}

编辑距离问题

• s是子序列
• 其实就是求最长公共子序列，如果s和t的公共子序列长度等于s的长度，那么s就是t的子序列

判断子序列 - LeetCode 392

• 定义dp数组：dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]。方便第一行第一列初始化
• 递推公式（状态转移方程）：if (s[i - 1] == t[j - 1])，那么dp[i][j] = dp[i - 1][j - 1] + 1，if (s[i - 1] != t[j - 1])，此时相当于t要删除元素，t如果把当前元素t[j - 1]删除，那么dp[i][j] 的数值就是 看s[i - 1]与 t[j - 2]的比较结果了，即：dp[i][j] = dp[i][j - 1]
• 初始化：从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]，所以dp[0][0]和dp[i][0]是一定要初始化的。
• 遍历顺序：根据递推公式 推倒方向得出

for(int i = 1; i <= length1; i++){
    for(int j = 1; j <= length2; j++){
        // 递推公式
    }
}
if(dp[length1][length2] == length1){
    return true;
}else{
    return false;
}

• 打印dp检查

public boolean isSubsequence(String s, String t) {
    int length1 = s.length(); int length2 = t.length();
    int[][] dp = new int[length1+1][length2+1];
    for(int i = 1; i <= length1; i++){
        for(int j = 1; j <= length2; j++){
            if(s.charAt(i-1) == t.charAt(j-1)){
                dp[i][j] = dp[i-1][j-1] + 1;
            }else{
                dp[i][j] = dp[i][j-1]; 
            }
        }
    }
    if(dp[length1][length2] == length1){
        return true;
    }else{
        return false;
    }
}

不同的子序列 （s有多少删除元素的方式能变成t？） - LeetCode 115

• 定义dp数组：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]
• 递推公式（状态转移方程）：当s[i - 1] 与 t[j - 1]相等时，dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; 当s[i - 1] 与 t[j - 1]不相等时，dp[i][j]只有一部分组成，不用s[i - 1]来匹配（就是模拟在s中删除这个元素），即：dp[i - 1][j]。所以dp[i][j] = dp[i - 1][j]
• 初始化：
  • dp[i][0]一定都是1，因为也就是把以i-1为结尾的s，删除所有元素，出现空字符串的个数就是1。
  • dp[0][j]一定都是0，s如论如何也变成不了t。
  • dp[0][0]应该是1，空字符串s，可以删除0个元素，变成空字符串t。
• 遍历顺序：

for (int i = 1; i <= s.size(); i++) {
    for (int j = 1; j <= t.size(); j++) {
        // 递推公式
    }
}
return dp[s.size()][t.size()];

• 打印dp检查

两个字符串的删除操作 （可以用删，问最少操作次数） - LeetCode 583

• 定义dp数组：dp[i][j]：以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。
• 递推公式（状态转移方程）：
  • 当word1[i - 1] 与 word2[j - 1]相同的时候，dp[i][j] = dp[i - 1][j - 1]; 因为不需要操作，可以从上一个位置推出当前结果
  • 当word1[i - 1] 与 word2[j - 1]不相同的时候，有三种情况：取最小值因为求的是最小操作次数
    • 情况一：删word1[i - 1]，最少操作次数为dp[i - 1][j] + 1
    • 情况二：删word2[j - 1]，最少操作次数为dp[i][j - 1] + 1
    • 情况三：同时删word1[i - 1]和word2[j - 1]，操作的最少次数为dp[i - 1][j - 1] + 2
• 初始化：dp[i][0]：word2为空字符串，以i-1为结尾的字符串word1要删除多少个元素，才能和word2相同呢，很明显dp[i][0] = i。dp[0][j]的话同理
• 遍历顺序：

for (int i = 1; i <= word1.size(); i++) {
            for (int j = 1; j <= word2.size(); j++) {
                // 递推公式
            }
}
return dp[word1.size()][word2.size()];

• 打印dp检查

编辑距离（可以用增删改，问最少操作次数） - LeetCode 72

• 定义dp数组：以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]
• 递推公式（状态转移方程）：
  • 当word1[i - 1] 与 word2[j - 1]相同的时候，dp[i][j] = dp[i - 1][j - 1];
  • 当word1[i - 1] 与 word2[j - 1]不相同的时候，有三种情况：取最小
    • 操作一：word1删除一个元素，那么就是以下标i - 2为结尾的word1 与 j-1为结尾的word2的最近编辑距离 再加上一个操作。即 dp[i][j] = dp[i - 1][j] + 1;
    • 操作二：word2删除一个元素，那么就是以下标i - 1为结尾的word1 与 j-2为结尾的word2的最近编辑距离 再加上一个操作。即 dp[i][j] = dp[i][j - 1] + 1;
      • word2添加一个元素，相当于word1删除一个元素
    • 一次替换的操作，就可以让 word1[i - 1] 和 word2[j - 1] 相同。 所以 dp[i][j] = dp[i - 1][j - 1] + 1;
• 初始化：dp[i][0]：word2为空字符串，以i-1为结尾的字符串word1要删除多少个元素，才能和word2相同呢，很明显dp[i][0] = i。dp[0][j]的话同理
• 遍历顺序：

for (int i = 1; i <= word1.size(); i++) {
            for (int j = 1; j <= word2.size(); j++) {
                // 递推公式
            }
}
return dp[word1.size()][word2.size()];

• 打印dp检查

public int minDistance(String word1, String word2) {
    int m = word1.length();
    int n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
    // 初始化
    for (int i = 1; i <= m; i++) {
        dp[i][0] =  i; 
    }
    for (int j = 1; j <= n; j++) {
        dp[0][j] = j;
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            // 因为dp数组有效位从1开始
            // 所以当前遍历到的字符串的位置为i-1 | j-1
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1; // java中min的参数是两个，所以需要嵌套两个min
            }
        }
    }
    return dp[m][n];
}

回文子串（要连续） - LeetCode 647

• 定义dp数组：区间范围[i,j] （注意是左闭右闭，包含）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。
• 递推公式（状态转移方程）：
  • s[i]与s[j]不相等，dp[i][j]一定是false
  • 相等 三种情况 定义一个result然后++
    • 情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
    • 情况二：下标i 与 j相差为1，例如aa，也是回文子串
    • 情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为true。
• 初始化：dp[i][j]初始化为false
• 遍历顺序：要从下到上，从左到右遍历，这样保证dp[i + 1][j - 1]都是经过计算的

for (int i = s.size() - 1; i >= 0; i--) {  // 注意遍历顺序
    for (int j = i; j < s.size(); j++) {
        // 递推公式
    }
}

• 打印dp检查

最长回文子序列（可以不连续） - LeetCode 516

• 定义dp数组：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。
• 递推公式（状态转移方程）：
  • 如果s[i]与s[j]相同，那么dp[i][j] = dp[i + 1][j - 1] + 2;
  • 如果s[i]与s[j]不相同，说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子序列的长度，那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列，即：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
• 初始化：当i与j相同，那么dp[i][j]一定是等于1的，即：一个字符的回文子序列长度就是1。dp[i][i] = 1
• 遍历顺序：dp[i][j] 依赖于 dp[i + 1][j - 1] ，dp[i + 1][j] 和 dp[i][j - 1]。从下到上遍历，这样才能保证下一行的数据是经过计算的。

for (int i = s.size() - 1; i >= 0; i--) {
    for (int j = i + 1; j < s.size(); j++) { //j=i已经初始化
        // 递推公式
    }
}
return dp[0][s.size() - 1]; //最终答案在右上角

• 打印dp检查
• 另一种解法：中心扩散法

public class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";

        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);     // 奇数长度中心
            int len2 = expandAroundCenter(s, i, i + 1); // 偶数长度中心
            int len = Math.max(len1, len2);
            if (len > end - start) { // 如果当前回文的长度大于end - start，则更新start和end
            // 两行代码能统一处理奇偶情况
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }

        return s.substring(start, end + 1);
    }

    private int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) { // 如果left和right在范围内，并且left和right的字符相同，则继续扩展
            left--; // 向左扩展
            right++; // 向右扩展
        }
        return right - left - 1; // 当前回文的长度
    }
}

马跳棋的跳法数量 - LeetCode 688

• 定义dp数组：dp[x][y][step] 表示从(0,0)到(x,y)用step步的方法数
• 递推公式：
  • 马可以跳到8个方向
  • 如果马跳到(x,y)，那么(x,y)可以跳到8个方向
  • 所以dp[x][y][step] = dp[x-1][y-2][step-1] + dp[x-1][y+2][step-1] + dp[x+1][y-2][step-1] + dp[x+1][y+2][step-1] + dp[x-2][y-1][step-1] + dp[x-2][y+1][step-1] + dp[x+2][y-1][step-1] + dp[x+2][y+1][step-1]
• 初始化：dp[0][0][0] = 1
• 遍历顺序：从(0,0)开始遍历

// 马的8个可能移动方向
int[] dx = {-2, -1, 1, 2, 2, 1, -1, -2};
int[] dy = {-1, -2, -2, -1, 1, 2, 2, 1};

// 动态规划填表
for (int step = 1; step <= k; step++) {
    for (int x = 0; x < 10; x++) {
        for (int y = 0; y < 10; y++) {
            // 尝试从8个方向跳到当前位置(x, y)
            for (int i = 0; i < 8; i++) {
                int prevX = x - dx[i];
                int prevY = y - dy[i];
                
                // 检查前一个位置是否在棋盘范围内
                if (prevX >= 0 && prevX < 10 && prevY >= 0 && prevY < 10) {
                    dp[x][y][step] += dp[prevX][prevY][step - 1]; // 把所有上一步（step-1）可以跳到 (x, y) 的位置 (prevX, prevY) 的跳法数，累加到当前位置的跳法数上。
                }
            }
        }
    }
}

打家劫舍

• 定义dp数组：dp[i]表示偷到第i个房子时，能偷到的最大金额
• 递推公式：dp[i] = max(dp[i-1], dp[i-2] + nums[i])，因为偷到第i个房子时，能偷到的最大金额等于偷到第i-1个房子时能偷到的最大金额和偷到第i-2个房子时能偷到的最大金额加上第i个房子的金额中的最大值
• 初始化：dp[0] = nums[0]，dp[1] = max(dp[0], nums[1])
• 遍历顺序：从2到n，因为偷到第0个房子时，能偷到的最大金额是nums[0]，偷到第1个房子时，能偷到的最大金额是max(dp[0], nums[1])
• 返回结果：dp[n]

public int rob(int[] nums) {
	if (nums == null || nums.length == 0) return 0; // 如果数组为空，则返回0
	if (nums.length == 1) return nums[0];
	int[] dp = new int[nums.length];
	dp[0] = nums[0];
	dp[1] = Math.max(dp[0], nums[1]); // 偷到第1个房子时，能偷到的最大金额是max(dp[0], nums[1])
	for (int i = 2; i < nums.length; i++) {
		dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]); // 偷到第i个房子时，能偷到的最大金额是max(偷到第i-1个房子时能偷到的最大金额, 偷到第i-2个房子时能偷到的最大金额加上第i个房子的金额)
	}
	return dp[nums.length - 1];
}

打家劫舍II

• 环形数组，所以需要考虑两种情况
  • 偷第一个房子，不偷最后一个房子
  • 不偷第一个房子，偷最后一个房子
• 所以需要分别计算两种情况的最大金额，然后取最大值

public int rob(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    if (nums.length == 1) return nums[0];
    return Math.max(
        robRange(nums, 0, nums.length - 2),  // 偷头不偷尾
        robRange(nums, 1, nums.length - 1)   // 不偷头偷尾
    );
}

private int robRange(int[] nums, int start, int end) {
    if (end == start) return nums[start]; // 如果只有一个房子，则直接返回该房子的金额
    int prev1 = nums[start]; 
    int prev2 = Math.max(nums[start], nums[start + 1]); 
    for (int i = start + 2; i <= end; i++) { // 从第三个房子开始遍历
        int curr = Math.max(prev2, prev1 + nums[i]); // 当前房子的最大金额是前两个房子的最大金额和当前房子的金额中的最大值
        prev1 = prev2; // 更新前两个房子的最大金额
        prev2 = curr; // 更新当前房子的最大金额
    }
    return prev2; // 返回最后一个房子的最大金额
}

打家劫舍III

• 二叉树，所以需要考虑两种情况
  • 偷当前节点，不偷子节点
  • 不偷当前节点，偷子节点
• 所以需要分别计算两种情况的最大金额，然后取最大值
• 后序遍历，因为通过递归函数的返回值来做下一步计算

class Solution {
    public int rob(TreeNode root) {
        int[] res = dfs(root); // 返回两个状态：res[0]：不偷当前节点能获得的最大金额，res[1]：偷当前节点能获得的最大金额
        return Math.max(res[0], res[1]);
    }

    /**
     * 返回两个状态：
     * res[0]：不偷当前节点能获得的最大金额
     * res[1]：偷当前节点能获得的最大金额
     */
    private int[] dfs(TreeNode node) {
        if (node == null) return new int[]{0, 0};

        int[] left = dfs(node.left); // 递归左子树
        int[] right = dfs(node.right); // 递归右子树

        // 不偷当前节点：左右孩子可以偷或不偷，取最大
        int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);

        // 偷当前节点：左右孩子不能偷
        int rob = node.val + left[0] + right[0];

        return new int[]{notRob, rob};
    }
}

单词拆分

• 定义dp数组：dp[i]表示字符串s的前i个字符是否可以被拆分成wordDict中的单词
• 递推公式：dp[i] = dp[j] && wordDictSet.contains(s.substring(j, i))，因为如果前j个字符可以被拆分成wordDict中的单词，并且第j+1到i个字符也在wordDict中，那么前i个字符也可以被拆分成wordDict中的单词
• 初始化：dp[0] = true，因为空字符串可以被拆分成wordDict中的单词
• 遍历顺序：从1到s.length()，因为需要遍历所有可能的拆分位置
• 返回结果：dp[s.length()]

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordDictSet = new HashSet(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true; 
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break; // 一旦找到一个可行的划分，就可以确定 dp[i] = true，无需继续循环，提前退出，提高效率。
                }
            }
        }
        return dp[s.length()];
    }
}

零钱兑换

• 定义dp数组：dp[i]表示凑成金额i所需的最少硬币数
• 递推公式：dp[i] = min(dp[i], dp[i - coins[j]] + 1)，因为如果凑成金额i所需的最少硬币数是dp[i]，那么凑成金额i-coins[j]所需的最少硬币数是dp[i - coins[j]]，所以dp[i] = min(dp[i], dp[i - coins[j]] + 1)
• 初始化：dp[j] = max，max 是 Integer.MAX_VALUE，表示凑不成金额i。然后 dp[0] = 0，因为凑成金额0所需的最少硬币数是0
• 遍历顺序：从1到amount，因为需要遍历所有可能的金额
• 返回结果：dp[amount]

public int coinChange(int[] coins, int amount) {
    int max = Integer.MAX_VALUE;
    int[] dp = new int[amount + 1];
    //初始化dp数组为最大值
    for (int j = 0; j < dp.length; j++) {
        dp[j] = max;
    }
    //当金额为0时需要的硬币数目为0
    dp[0] = 0;
    for (int i = 0; i < coins.length; i++) {
        //正序遍历：完全背包每个硬币可以选择多次
        for (int j = coins[i]; j <= amount; j++) {
            //dp[j - coins[i]] 表示：在没有当前这枚硬币的情况下，是否能够凑出 j - coins[i]。
            //如果这个值还是初始值 max，说明该金额无法构造 → 不做更新。
            //否则，可以通过"构造 j - coins[i] 后再加上一枚 coins[i]"来构造出 j。
            if (dp[j - coins[i]] != max) {
                //选择硬币数目最小的情况
                dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
            }
        }
    }
    return dp[amount] == max ? -1 : dp[amount];
}

遍历顺序判断

• 组合问题：外层for循环遍历物品，内层for循环遍历背包
• 排列问题：外层for循环遍历背包，内层for循环遍历物品

最小路径和

• 每次只能向下或者向右移动一步。

public int minPathSum(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    int[][] dp = new int[m][n];

    dp[0][0] = grid[0][0]; // 初始化起点

    // 初始化第一行
    for (int j = 1; j < n; j++) {
        dp[0][j] = dp[0][j - 1] + grid[0][j]; // 第一行只能从左边过来
    }

    // 初始化第一列
    for (int i = 1; i < m; i++) {
        dp[i][0] = dp[i - 1][0] + grid[i][0]; // 第一列只能从上边过来
    }

    // 状态转移
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]); // 当前位置的值加上左边和上边最小的值
        }
    }

    return dp[m - 1][n - 1];
}

最大正方形

class Solution {
    public int maximalSquare(char[][] matrix) {
        int maxSide = 0; // 记录最大正方形的边长
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return maxSide; // 如果矩阵为空，返回0
        }
        int rows = matrix.length, columns = matrix[0].length; // 矩阵的行数和列数
        int[][] dp = new int[rows][columns]; // 定义dp数组，dp[i][j]表示以(i,j)为右下角的最大正方形的边长
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (matrix[i][j] == '1') { // 如果当前位置是1
                    if (i == 0 || j == 0) { // 如果当前位置是第一行或第一列, 不需要考虑左、上、左上，因为这些位置不存在
                        dp[i][j] = 1; // 最大正方形的边长为1
                    } else {
                        dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1; // 最大正方形的边长为左、上、左上三个位置的最小值加1
                    }
                    maxSide = Math.max(maxSide, dp[i][j]); // 更新最大正方形的边长
                }
            }
        }
        return maxSide * maxSide; // 返回最大正方形的面积
    }
}

乘积最大子数组

class Solution {
    public int maxProduct(int[] nums) {
        long maxF = nums[0], minF = nums[0]; // 需要初始化最小值，因为如果数组中包含负数，那么最大值和最小值会交换
        int ans = nums[0];
        for (int i = 1; i < nums.length; i++) {
            long mx = maxF, mn = minF; // 保存当前最大值和最小值
            maxF = Math.max(nums[i], Math.max(mx * nums[i], mn * nums[i])); // 更新最大值
            minF = Math.min(nums[i], Math.min(mx * nums[i], mn * nums[i])); // 更新最小值
            ans = Math.max(ans, (int)maxF); // 更新结果
        }
        return ans; // 返回结果
    }
}

最长的斐波那契子序列

• 斐波那契样式：对任意相邻三个数 x, y, z，必须满足 x + y = z。
• 所以我们用 DP + 哈希表 优化到 O(n²)。
• dp[j][i] = 以 A[j], A[i] 结尾的最长斐波那契子序列长度。
• 状态转移方程：
  • 如果 arr[i] - arr[j] 在哈希表中且索引小于 j，则 dp[j][i] = dp[k][j] + 1。
  • 否则，dp[j][i] = 2，因为至少有 A[j], A[i] 两个元素。
• 初始化：dp[j][i] = 2，因为至少有 A[j], A[i] 两个元素。
• 遍历顺序：从左到右，从上到下。
• 返回结果：res>=3?res:0，因为斐波那契子序列长度至少为3。

public int lenLongestFibSubseq(int[] arr) {
    int n = arr.length;
    Map<Integer,Integer> idx = new HashMap<>(); // 存储每个元素的索引 key: arr[i], value: i
    for(int i = 0; i<n; i++){ // 遍历数组，存储每个元素的索引
        idx.put(arr[i],i);
    }
    int[][] dp = new int[n][n];
    int res = 0;
    for(int i = 0; i<n; i++){
        for(int j = 0; j<i; j++){
            int prev = arr[i]-arr[j]; // 计算斐波那契数列的前一个数
            Integer k = idx.get(prev); // 获取斐波那契数列的前一个数的索引
            if(k!=null && k<j){ // 如果斐波那契数列的前一个数的索引存在，并且小于j
                dp[j][i] = dp[k][j]+1; // 更新dp[j][i]
            }else{
                dp[j][i] = 2; // 如果斐波那契数列的前一个数的索引不存在，或者大于j，则dp[j][i]为2
            }
            res = Math.max(res,dp[j][i]); // 更新结果
        }
    }
    return res>=3?res:0; // 如果结果小于3，则返回0，否则返回结果
}

打家劫舍III - LeetCode 337

// ... existing code ...

单词拆分 - LeetCode 139

// ... existing code ...

零钱兑换 - LeetCode 322

// ... existing code ...

最小路径和 - LeetCode 64

// ... existing code ...

最大正方形 - LeetCode 221

// ... existing code ...

乘积最大子数组 - LeetCode 152

// ... existing code ...

最长的斐波那契子序列 - LeetCode 873

// ... existing code ...