动态规划

最长重复子数组[🔥64]

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        //dp吧
        //dp数组表示什么? : 以 i结尾的nums1 以j 结尾的nums2 ，最大的子数组长度
        //遍历顺序
        //状态方程
        //dp数组就表示 
        // 1 2 3 4
        // 1 2 3 5

        // 1 2 3 4 6
        // 1 2 5 4 
        int [][]dp  = new int[nums1.length+1][nums2.length+1];
        int res=0;
        for(int i=0;i<nums1.length;i++){
            for(int j=0;j<nums2.length;j++){
                if(nums1[i]==nums2[j]){
                    dp[i+1][j+1]=dp[i][j]+1;
                    res=Math.max(res,dp[i+1][j+1]);
                }
            }
        }
        return res;
    }
}

买卖股票的最佳时机 II [82]

题目：

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润

思路：

1. 贪心：低价买入，如果第二天高价就卖出，局部最优解

class Solution {
    public int maxProfit(int[] prices) {
        int res =0;
        //上帝视角看
        //我们要实现最大利润，那么从股票走势图来看就是 递增的每一段我都要赚，只要第二天涨价我就卖，每一段上升期我都吃
        for(int i=1;i<prices.length;i++){
            if(prices[i]-prices[i-1]>0){
                res+=prices[i]-prices[i-1];
            }
        }
        return res;
    }
}

2. 动态规划：状态：有股票or没股票，dp数组含义：第i天持有or没持有股票的最大利润，状态推导

class Solution {
    public int maxProfit(int[] prices) {
        //dp : i 这一天可获得的最大利润
        // 股票状态：有或者没有
        int [][] dp = new int[prices.length][2];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for(int i=1;i<prices.length;i++){
            //0:有：昨天有今天继续持有 or 昨天没有但今天买入
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);
            //1:没有：昨天没有今天继续没有 or 昨天有但今天卖出
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);
        }
        //因为最后一天手里 不能有股票 才是最大利润（卖掉股票才是真实收益）。
        return dp[prices.length-1][1];
    }
}

不同路径[72]

思路：DP，四部曲 ，数组含义，初始化，状态，推导

class Solution {
    public int uniquePaths(int m, int n) {
        //dp：表示达到该位置i j最大有多少条路径
        int [][] dp = new int[m][n];
        //初始化
        dp[0][0]=1;
        for(int i=1;i<m;i++){
            dp[i][0]=1;
        }
        for(int j=1;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];
    }
}

编辑距离[183]

思路：

1. 背诵 哈哈哈

class Solution {
    public int minDistance(String word1, String word2) {
        int [][]dp=new int[word1.length()+1][word2.length()+1];
        //dp[i][j]  表示 word 中前 i个字符，变换到word2中的 前j个字符，需要的最小次数
        // dp[0][0] 表示 空字符串

        //
        for(int i=0;i<=word1.length();i++){
           dp[i][0]=i;
        }
        for(int j=0;j<=word2.length();j++){
            dp[0][j]=j;
        }
        for(int i=1;i<=word1.length();i++){
            for(int j=1;j<=word2.length();j++){
                
                //eg：
                // ros i=2
                // rs i=1
                //特殊情况 word1[i-1]==word[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(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
            }
        }
        return dp[word1.length()][word2.length()];
    }
}

爬楼梯

思路：

1. 动态规划，思考dp数组含义，当前状态是怎么由前一个状态推导过来的
2. //两种情况：比如我在三阶梯，我可以从一阶梯一下子两步上来，以及从二阶梯一步上来

class Solution {
    public int climbStairs(int n) {
        if(n < 2) return n; 
        int []dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        //4
        //1:1
        //2:2
        //3: 2
        for(int i = 3;i <= n;i++){
            //两种情况：比如我在三阶梯，我可以从一阶梯一下子两步上来，以及从二阶梯一步上来
            dp[i] = dp[i-1] + dp[i-2]; 
        }
        return dp[n];
    }
}

零钱兑换

class Solution {
    public int coinChange(int[] coins, int amount) {
        //dp数组含义： 构成当前金额的最小硬币数
        //dp[i] = dp[ i - cions ] + 1 
        if(amount <= 0){
            return 0;
        }
        int []dp = new int[amount+1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0] = 0;
        for(int i = 0;i < dp.length;i++){
            for(int j = 0;j<coins.length;j++){
                if( i - coins[j] >= 0 && dp[i-coins[j]] != Integer.MAX_VALUE){
                    dp[i] = Math.min(dp[i-coins[j]] + 1, dp[i]);
                }
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[amount] == Integer.MAX_VALUE? -1: dp[amount];
    }
}

最大正方形[81]

思路：动态规划

就嗯记，dp思路 相邻三个矩形边长的最小值+1

dp数组含义即 以matrix[i][j] 为右下角为右下角的最大正方形边长

class Solution {
    public int maximalSquare(char[][] matrix) { 
        int n = matrix.length;
        int m = matrix[0].length;
        //dp数组含义 dp[i][j] 表示：以 matrix[i][j] 为右下角的最大正方形边长。
        int[][] dp = new int[n][m];
        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(matrix[i][j] == '1') {
                    if(i == 0|| j == 0){
                        dp[i][j] = 1;
                    }
                    //min (相邻三个正方形) + 1
                    else dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
                    res = Math.max(res, dp[i][j]);
                }
            }
        }
        return res * res;
    }
}

打家劫舍[70]

思路：

1. 动规，详情见代码

class Solution {
    public int rob(int[] nums) {
        if(nums.length == 1) return nums[0];
        int []dp = new int[nums.length];
        //dp数组含义 小偷走到当前i index房子时 能偷的最高金额
        //初始化
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        int res = dp[1];
        for(int i = 2;i < nums.length; i++){
            //两种情况 偷 or 不偷，且不能相邻偷
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

输出路径

class Solution {
    public int rob(int[] nums) {
        if(nums.length == 1) return nums[0];
        int []dp = new int[nums.length];
        //dp数组含义 小偷走到当前i index房子时 能偷的最高金额
        //初始化
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        int res = dp[1];
        
        //路径
        List<Integer> resList = new ArrayList<>(); 
        //resList.add();
        for(int i = 2;i < nums.length; i++){
            //偷 or 不偷
            if(dp[i - 2] + nums[i] > dp[i - 1]){
                if(i == 2) resList.add(dp[0]);
                resList.add(nums[i]);
            }
            //两种情况 偷 or 不偷，且不能相邻偷
            dp[i] = Math.max(dp[i-2] + nums[i], dp[i - 1]);
            res = Math.max(res, dp[i]);
        }
        System.out.println(resList);
        return res;
    }
}

单词拆分[64]

思路：

1. DP做法：看成背包问题，即s是否可以被物品wordDict装满
2. 那么这时候dp数组的含义：dp[i] 表示0….i 范围的s是否可以被worddict里的单词分隔
3. 这种做法时间复杂度 O（）？不太行哦
4. 时间复杂度：O(n³)

• n = 字符串长度
• 因为三层操作：外层 i、内层 j、substring 复制

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        //dp数组含义 以i为结尾的字符串，是否可以被转换
        HashSet<String> set = new HashSet(wordDict);
        boolean[] dp = new boolean[s.length()];
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j <= i; j++) {
                //j...i
                String sub = s.substring(j, i + 1);
                // 0...j...i
                //这里的条件成立为两部分：[0..j-1] [j...i] 可以被分隔
                //两者共同使 以i为结尾的字符串，是否可以被转换
                if ((j == 0 || dp[j - 1]) && set.contains(sub)) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length() - 1];
    }
}

https://chatgpt.com/s/t_68ea8e7831c48191ba35865a1392cdee

分割等和子集[28]

思路

1. 可能性问题可以优先想到 DP
2. 必会题，01背包
3. dp[i][j] 表示[0..i]里若干个元素是否可以构成和为j

class Solution {
    public boolean canPartition(int[] nums) {
        int sum=0;
        for(int i=0;i<nums.length;i++) sum+=nums[i];
        int avg =sum/2;
        if(sum % 2 == 1) return false;
        //dp数组含义：nums[0.。i]  是否存在若干个元素的和 等于 j
        boolean [][]dp = new boolean[nums.length][avg + 1];
        //初始化
        if(nums[0] <= avg){
            dp[0][nums[0]] = true;
        }
        for(int i = 1; i < nums.length; i++){
            for(int j = 0; j <= avg; j++){
                //j为 目标和
                if(nums[i] <= j){
                    //不选 则 [0....i-1]若干个元素和为j
                    //选，则[0....i-1]若干个元素和为j-nums[i]
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]]; 
                }
                //nums[i] 本身超过了 j,那肯定是不选的
                else dp[i][j] = dp[i - 1][j];
            }
            if(dp[i][avg]) return true;
        }
        return dp[nums.length - 1][avg];
    }
}

压缩：

class Solution {
    public boolean canPartition(int[] nums) {
        int sum=0;
        for(int i=0;i<nums.length;i++) sum+=nums[i];
        int avg =sum/2;
        if(sum % 2 == 1) return false;
        //dp数组含义：是否存在若干个元素的和 等于 i
        boolean []dp = new boolean[avg + 1];
        if(nums[0] <= avg) dp[nums[0]] = true;
        //初始化
        for(int i = 1; i < nums.length; i++){
            for(int j = avg; j >= 0; j--){
                if(nums[i] <= j) dp[j] = dp[j] || dp[j - nums[i]];
            }
            if(dp[avg]) return true;
        }
        return dp[avg];
    }
}

分割成和最相近的两个子集

完全平方数[22]

完全背包

class Solution {
    // 和为 n 的完全平方数的最少数量
    // 
    /**
    dp数组含义  和为 i 的完全平方数的最少数量 
    
     */
    public int numSquares(int n) {
        if (n <= 3)
            return n;
        int length = n / 2;
        int[] nums = new int[length];
        int count = 1;
        for (int i = 0; i < nums.length; i++, count++) {
            nums[i] = count * count;
        }
        //System.out.println(Arrays.toString(nums));
        int dp[] = new int[n + 1];
        dp[0] = 0;
        for (int i = 1; i < dp.length; i++)
            dp[i] = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j <= n; j++) {
                if (j >= nums[i] && dp[j - nums[i]] != Integer.MAX_VALUE)
                    dp[j] = Math.min(dp[j], dp[j - nums[i]] + 1);
            }
        }
        //System.out.println(Arrays.toString(dp));
        return dp[n];
    }
}

目标和

打家劫舍 III[]

思路

1. 树形DP，树的每个节点存储两种状态（抢or不抢），然后从底递推到 根节点
2. 当前节点抢，则 left不抢 + right不抢 + 1
3. 若当前节点不抢，则左右节点的抢or不抢中取最大，然后相加。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int rob(TreeNode root) {
        int[] res = dfs(root);
        //最后这里，就是当前节点抢不抢的问题
        return Math.max(res[0], res[1]);
    }
    public int[] dfs(TreeNode root){
        if(root == null){
            return new int[]{0,0}; //怎么选都是没有的
        }
        int []left = dfs(root.left);
        int []right = dfs(root.right);
        //当前节点抢，则 左右子节点必须为 不抢的
        int rob = left[1] + right[1] + root.val; 
        //当前节点不抢，则 从左右子节点取 最大的，然后一起带上来当前节点
        int noRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return new int[]{rob, noRob};
    } 
}

买卖股票的最佳时机含冷冻期[4]

思路

1. 两个状态：持有or不持有
2. dp数组含义 第i 持有or不持有股票 的最大利润
3. 状态机DP

class Solution {
    public int maxProfit(int[] prices) {
        //status: 0 没持有 1 持有
        // 有冻结期 无非就是 今天卖出 明天不能买入、
        //prices 是指同一只股票的价格啊！！！！！   
        //dp数组含义：第i天 没持有or持有 的利润
        int[][] dp = new int[prices.length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < prices.length; i++) {

            //没持有，可能是 继续没持有，或者 在昨天持有股票的基础上 在今天以今天股票的价格股票给卖了
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);


            //持有：可能是继续持有股票 或者是 前天把股票卖出了，然后以今天以今天股票的价格把股票买入了（为什么只能前天，因为不能昨天卖出，然后第二天买入）
            //不能同时拥有多只股票，其实只有一直股票
            if (i == 1)
                dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
            else
                //不能同时参与多笔交易
                
                dp[i][1] = Math.max(dp[i - 1][1], dp[i - 2][0] - prices[i]);
            
            
        }
        //最后肯定得把股票卖了，即没持有，才能实现利益最大化
        return dp[prices.length - 1][0];
    }
}

比特位计数[2]

思路

1. dp含义：第数为i，二进制后1的个数为 dp[i]
2. 递推公式：当i为偶数，当i为奇数

class Solution {
    public int[] countBits(int n) {
        //0 -> 0
        //1 -> 1
        //2 -> 10
        //3 -> 11 3/2 == 1 & 1 
        //4 -> 100 4/2 == 2 
        //5 -> 101 5/2 == 2
        //6 -> 110
        //7 -> 111 
        //8 -> 1000 2的3次方 8/2 == 3
        int[] res = new int[n + 1];
        if(n < 1) return res; 
        res[0] = 0;
        res[1] = 1;
        for(int i = 2; i <= n; i++){
            int num = i;
            if(num % 2 == 0){
                res[i] = res[num / 2];
            }
            else {
                res[i] = res[num / 2] + 1;
            }

        }
        return res;
    }
}