力扣hot100—动态规划&多维动态规划15题

爬楼梯

爬第n阶楼梯的方法数量，等于 2 部分之和：

爬上 n−1 阶楼梯的方法数量。因为再爬1阶就能到第n阶
爬上 n−2 阶楼梯的方法数量，因为再爬2阶就能到第n阶

class Solution {
    public int climbStairs(int n) {
        // dp[i] 表示爬到第i层台阶的方法有多少种
        int[] dp = new int[n+2];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i <=n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
}

杨辉三角

把杨辉三角的每一排左对齐，就方便看了。
[1]
[1,1]
[1,2,1]
[1,3,3,1]
[1,4,6,4,1]

每一排的第一个数和最后一个数都是 1。
其余数字，等于左上方的数，加上正上方的数。

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        res.add(List.of(1));
        for(int i = 1; i < numRows; i++){
            List<Integer> row = new ArrayList<>();
            row.add(1);
            for(int j = 1; j < i; j++){
                // i表示当前层 j表示当且列
                row.add(res.get(i-1).get(j-1) + res.get(i-1).get(j));
            }
            row.add(1);
            res.add(row);
        }
        return res;
    }
}

打家劫舍

# ===============最简单想法=============
# dp[i][1]表示偷第i间房的最大金额，dp[i][0]表示不偷这间房的最大金额
# 递推关系
# ① dp[i][1] = dp[i-1][0] + nums[i] # 偷这间房 则上一次肯定不能偷
# ② dp[i][0] = max(dp[i-1][0], dp[i-1][1]) # 不偷这间房的最大，则是上一次不管偷不偷的最大
# ===============优化===============================
# 若dp[i]表示直到第i间房的最大金额 
# 首先明确dp[i][0] = dp[i-1]  因为第i个房间不偷的最大金额就等于第i-1个房间的最大金额
# 则上面式子可以表示为
# ① dp[i][1] = dp[i-2] + nums[i][因为dp[i-1][0] = max(dp[i-2][0],dp[i-2][1])==dp[i-2]]
# ② dp[i][0] = dp[i-1]
# 故dp[i] = max(dp[i][1],dp[i][0])= max(dp[i-2] + nums[i], dp[i-1])
# 从而得到递推关系

class Solution {
    public int rob(int[] nums) {
        int[] dp = new int[nums.length + 10];
        // dp[i] 表示到第i家偷到的最多钱
        dp[0] = nums[0];
        if(nums.length == 1) return dp[0];
        dp[1] = Math.max(dp[0], nums[1]);
        for(int i = 2; i<nums.length; i++){
            // 到第i家偷的最多的钱 等于i-2+现在这家的最多钱 or 到第i-1家的最多钱
            dp[i] = Math.max(dp[i-2] + nums[i], dp[i-1]);
        }
        return dp[nums.length-1];
    }
}

完全平方数

法1：DFS暴力回溯，会超时。

class Solution {
    public int numSquares(int n) {
        return dfs(n);
    }

    private int dfs(int n) {
        if (n <= 0) {
            return 0;
        }
        int count = Integer.MAX_VALUE;
        //依次减去一个平方数
        for (int i = 1; i * i <= n; i++) {
            //选最小的
            count = Math.min(count, dfs(n - i * i) + 1);
        }
        return count;
    }
}

法2：DP

import java.util.*;
class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                // 状态转移：dp[i] = min(dp[i], dp[i - j*j] + 1)
                // 第i个数的完全平方数 等于 dp[i] 和 第i-j*j个数的完全平方数+1 二者的最小值
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        
        return dp[n];
    }
}

零钱兑换

仍可以用回溯法，不过会超时。

class Solution {
    int res = Integer.MAX_VALUE;
    public int coinChange(int[] coins, int amount) {
        if(coins.length == 0){
            return -1;
        }
        dfs(coins, amount, 0);
        if( res == Integer.MAX_VALUE) return -1;
        return res;
    }
    public void dfs(int[] coins, int amount, int cnt){
        // amout 小于 0 说明组成不了结果
        if(amount < 0){
            return;
        } 
        if(amount == 0){
            // 组成的了最小值
            res = Math.min(res, cnt);
        }
        for(int i = 0; i < coins.length; i++){
            dfs(coins, amount - coins[i], cnt+1);
        }
    }
}

动态规划方法：

class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, max);
        dp[0] = 0;
        for(int i = 1; i<=amount; i++){
            for(int j = 0; j<coins.length; j++){
                // 只判断coins[j] <= i的情况 即钱还没超限的情况
                if(coins[j] <= i){
                    // 满足i块钱的最小次数为dp[i-coins[j]] + 1
                    // 满足i块钱的最小次数 = 满足i-coins[j]块钱的最小次数 加上j这一次
                    dp[i] = Math.min(dp[i], dp[i-coins[j]] + 1);
                }
            }            
        }
        
        return dp[amount] > amount? -1: dp[amount];
    }
}

单词拆分

dp[i]表示字符串 s的前 i个字符（即 s[0..i-1]）是否可以被拆分成字典中的单词。

定义状态：dp[i]表示字符串 s的前 i个字符（即 s[0..i-1]）是否可以被拆分成字典中的单词。

状态转移：

对于每个位置 i（从 1 到 s.length），我们尝试所有可能的切分点 j（0 ≤ j < i）。
如果 dp[j]为 true，说明 s[0..j-1]可以被拆分，那么检查子串 s[j..i-1]是否在 wordDict中。
如果在，则说明 s[0..i-1]也能被拆分，即 dp[i] = true，并可以提前结束对当前 i的枚举。

初始条件：dp[0] = true，因为空字符串默认是可以被拆分的（即不选任何单词）。

import java.util.*;

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // 把List set化 便于后面查找
        Set<String> wordSet = new HashSet<>(wordDict);
        int n = s.length();
        // dp[i] 表示字符串s的前i个字符（即 s[0..i-1]）是否可以被拆分成字典中的单词。
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;

        // 对于每个位置i 尝试每种切分可能点j
        // dp[j] = true 表示 s[0..j-1]是可以被拆分
        // 此时可以检查下s[j..i-1]是不是也能匹配上字典中的单词
        // 如果满足 dp[j] = true 且 s[j...i-1]也可以被拆分 说明dp[i] 可以被拆分
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break; // 找到一个拆分方式即可
                }
            }
        }
        return dp[n];
    }
}

最长递增子序列

定义 dp[i] 为考虑前 i 个元素，以第 i 个数字结尾的最长上升子序列的长度，注意 nums[i] 必须被选取。

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int maxans = 1;
        for (int i = 1; i < nums.length; i++) {
            // dp[i]表示以第i个数字为结尾的最递增子序列的长度
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                // i 大于 j 可以更新最长的上升子序列
                if (nums[i] > nums[j]) {
                    // dp[i] = Max(dp[i], j的最长上升子序列+1)
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxans = Math.max(maxans, dp[i]);
        }
        return maxans;
    }
}

乘积最大子数组

需要同时维护最大值和最小值

状态定义：

maxDP[i]：以第 i 个元素结尾的连续子数组的最大乘积。
minDP[i]：以第 i 个元素结尾的连续子数组的最小乘积。

状态转移：

如果 nums[i]是正数：
- 乘上之前的最大乘积会更大，乘上之前的最小乘积会更小。
如果 nums[i]是负数：
- 乘上之前的最大乘积会变小（变最小），乘上之前的最小乘积会变大（变最大）。
如果 nums[i]是 0：
- 最大和最小都会变成 0。

所以状态转移方程，统一处理为：

// 到i的最大乘积子数组 要么是numsi本身，要么是i-1的最大值x numsi（如果numsi大于0），要么是i-1的最小值x numsi（如果numsi小于0）
maxDP[i] = max(nums[i], maxDP[i-1] * nums[i], minDP[i-1] * nums[i])
// 同样维护最小值
minDP[i] = min(nums[i], maxDP[i-1] * nums[i], minDP[i-1] * nums[i])

最后，题解如下，因为维护的是整个序列的最大值，所以，不需要存过程。

class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        // 目前的最大值和最小值数字
        int maxDP = nums[0];
        int minDP = nums[0];
        int res = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            int curr = nums[i];
            // 如果当前数是负数
            if (curr < 0) {
                // 最大值 要么是当前值 要么就是最小值 x 当前值
                // 最小值 要么是当前值 要么就是最大值（先前的） x 当前值
                int temp = maxDP;
                maxDP = Math.max(curr, minDP * curr);
                minDP = Math.min(curr, temp * curr);
            }else{
                // 正数很直观
                maxDP = Math.max(curr, maxDP * curr);
                minDP = Math.min(curr, minDP * curr);
            }
            res = Math.max(res, maxDP);
        }
        
        return res;
    }
}

分割等和子集

可以分析为01背包问题。

动态规划定义：定义 dp[i][j]为：考虑前 i个物品（数组元素），能否恰好装满容量 j。

对于dp[i][j]，状态转移：

不选第 i个物品：dp[i][j] = dp[i-1][j]

选第 i个物品：如果 j >= nums[i-1]，则 dp[i][j] = dp[i-1][j - nums[i-1]]两者取或运算。

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        // 如果总和是奇数 直接return false
        if (sum % 2 != 0) return false;
        int target = sum / 2;
        // dp[i][j]: 前 i 个数能否凑出 j
        boolean[][] dp = new boolean[nums.length + 1][target + 1];
        dp[0][0] = true;
        for (int i = 1; i <= nums.length; i++) {
            int num = nums[i - 1];
            for (int j = 0; j <= target; j++) {
                if (j >= num) {
                    // j>=num 则dp[i][j]= 要么不拿第i个物品凑成j个数；要么拿第i个物品凑成j个数
                    dp[i][j] = dp[i-1][j] || dp[i - 1][j - num];
                }else{
                    // j 小于num 只能等于不选第i个物品凑成j个数的
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        // 表示到遍历到第n个 拿了第n个物品 凑成了target目标
        return dp[nums.length][target];
    }
}

最长有效括号

维护一个栈，对于遇到的每个 ‘(’ ，将它的下标放入栈中

对于遇到的每个 )，我们先弹出栈顶元素表示匹配了当前右括号：
如果栈为空，说明当前的右括号为没有被匹配的右括号，把当前的)的下标，放入栈中更新
如果栈不为空，当前右括号的下标减去栈顶元素下标，即为以该右括号为结尾的最长有效括号的长度

class Solution {
    public int longestValidParentheses(String s) {
        if(s.length() <= 1) return 0;
        int max = 0;
        Deque<Integer> stk =new LinkedList<>();
        // 先预存-1 长度就是下标直接相减 不用额外+1 
        stk.offerLast(-1);
        for(int i = 0; i < s.length(); i++){
            // 左括号 下标入栈
            if(s.charAt(i) == '('){
                stk.offerLast(i);
            }else{
                // 遇到右括号 下标先出栈
                stk.pollLast();
                if(stk.isEmpty()){
                    // 为空了 说明不匹配 更新右括号下标
                    stk.offerLast(i);
                }else{
                    max = Math.max(max, i - stk.peekLast());
                }
            }
        }
        return max;
    }
}

不同路径

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[105][105];
        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++){
                // 到i,j点的走法 要么就是从i-1,j 往下走, 要么就是从i,j-1往右走
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}

最小路径和

思路同上，都较为简单。

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        if(m == 0) return 0;
        int n = grid[0].length;
        int[][] dp = new int[205][205];
        dp[0][0] = grid[0][0];
        for(int i = 1; i < m; i++){
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        for(int i = 1; i < n; i++){
            dp[0][i] = dp[0][i-1] + grid[0][i];
        }

        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                // 要么是从上最小 要么是从左最小
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
            }
        }
         return dp[m-1][n-1];
    }
}

最长回文子串

边界条件比较复杂。

不想DP方法了，直接字符串处理，中心扩散法。遍历字符串的每个位置，以该位置为中心向两边扩展，判断是否为回文，并记录最长回文子串。

需要考虑两种情况：

奇数长度回文：以单个字符为中心，如 "aba"。
偶数长度回文：以两个字符之间的空隙为中心，如 "abba"。

步骤：

遍历每个索引 i：
- 以 i为中心向左右扩展，得到奇数长度回文。
- 以 i和 i+1之间的空隙为中心向左右扩展，得到偶数长度回文。
每次扩展时，若左右字符相同则继续扩展，否则停止。
更新记录的最长回文起始位置和长度。

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) {
                // 如果最长的有变化 更新start和end
                // len-1是考虑len为偶数时情况 
                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++;
        }
        return right - left - 1;  // 回文长度
    }
}

最长公共子序列

定义 dp数组，大小为 (len(text1) + 1) * (len(text2) + 1)，其中 dp[0][j]和 dp[i][0]都初始化为 0（表示一个空字符串与另一个字符串的公共子序列长度为 0）。

遍历 text1和 text2的每个字符：如果 text1[i-1] == text2[j-1]，说明当前字符在公共子序列中，所以 dp[i][j] = dp[i-1][j-1] + 1。如果 text1[i-1] != text2[j-1]，说明当前字符不同，那么最长公共子序列可能来自 text1的前 i-1个字符和 text2的前 j个字符，或者 text1的前 i个字符和 text2的前 j-1个字符，取两者的最大值：dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        // dp[i][j]表示text1的前i个字符和text2的前j个字符的最长公共子序列的长度。
        int[][] dp = new int[m+5][n+5];
        for(int i = 1; i <=m; i++){
            char c1 = text1.charAt(i-1);
            for(int j = 1; j <=n; j++){
                char c2 = text2.charAt(j-1);
                if(c1 == c2){
                    // 如果text1的第i个 == text2的第j个 那么dp[i][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[m][n];
    }
}

编辑距离

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        // 将 word1的前 i个字符转换成 word2的前 j个字符所需的最少操作数。
        int[][] dp = new int[m + 1][n + 1];
        
        // 初始化
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i; // 删除 i 次
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j; // 插入 j 次
        }
        
        // 状态转移
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    // 如果word1的i词和word2的j词相等 就不需要编辑
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // i词和j词不等 有三种操作：要么替换、要么删除、要么插入
                    // 替换 就相当于匹配 i-1和j-1的次数 再加上替换这一次的操作
                    int replace = dp[i - 1][j - 1] + 1;

                    // i词和j词不等 i删除一个词 
                    // 删除 word1的第 i个字符（即 word1[i-1]），然后让剩下的部分去匹配 word2。删除操作额外+1
                    int delete = dp[i - 1][j] + 1;

                    // i词和j词不等 要加一个词 相当于j删一个词
                    // 相当于j删了一个词 就和上面的思想一样了
                    int insert = dp[i][j - 1] + 1;
                    dp[i][j] = Math.min(replace, Math.min(delete, insert));
                }
            }
        }
        
        return dp[m][n];
    }
}

爬楼梯