Dynamic Programming选编(2)

labuladong

787. Cheapest Flights Within K Stops

加权有向图中求最短路径
同时要满足，这条路径最多不能超过 K + 1 条边（经过 K 个节点相当于经过 K + 1 条边）。

BFS 算法相当于从起始点开始，一步一步向外扩散，那当然是离起点越近的节点越先被遍历到，如果 BFS 遍历的过程中遇到终点，那么走的肯定是最短路径。
对于加权图的最短路径来说，普通的队列不管用了，得用优先级队列 PriorityQueue

Dijkstra算法，从某一点到其余点的最短路径

从起点 src 出发，k 步之内（一步就是一条边）到达节点 s 的最小路径权重为 dp(s, k)

10. Regular Expression Matching

if (s[i] == p[j] || p[j] == '.') {
    // 匹配
    if (j < p.size() - 1 && p[j + 1] == '*') {
        // 有 * 通配符，可以匹配 0 次或多次
    } else {
        // 无 * 通配符，老老实实匹配 1 次
        i++; j++;
    }
} else {
    // 不匹配
    if (j < p.size() - 1 && p[j + 1] == '*') {
        // 有 * 通配符，只能匹配 0 次
    } else {
        // 无 * 通配符，匹配无法进行下去了
        return false;
    }
}

难点：

通配符匹配多次？
- 前提：模式串*的前一个字符能够跟文本串的末位匹配上
- 匹配多次，即先匹配一次，再继续匹配，模式串指针不动，文本串指针前移

class Solution {
    public boolean isMatch(String s, String p) {
        char[] cs = s.toCharArray();
        char[] cp = p.toCharArray();

        // dp[i][j]:表示s的前i个字符，p的前j个字符是否能够匹配
        boolean[][] dp = new boolean[cs.length + 1][cp.length + 1];

        // 初期值
        // s为空，p为空，能匹配上
        dp[0][0] = true;
        // p为空，s不为空，必为false(boolean数组默认值为false，无需处理)

        // s为空，p不为空，由于*可以匹配0个字符，所以有可能为true
        for (int j = 1; j <= cp.length; j++) {
            if (cp[j - 1] == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }

        // 填格子
        for (int i = 1; i <= cs.length; i++) {
            for (int j = 1; j <= cp.length; j++) {
                // 文本串和模式串末位字符能匹配上
                if (cs[i - 1] == cp[j - 1] || cp[j - 1] == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (cp[j - 1] == '*') { // 模式串末位是*
                    // 模式串*的前一个字符能够跟文本串的末位匹配上
                    if (cs[i - 1] == cp[j - 2] || cp[j - 2] == '.') {
                        dp[i][j] = dp[i][j - 2]      // *匹配0次的情况
                                || dp[i - 1][j];     // *匹配1次或多次的情况
                    } else { // 模式串*的前一个字符不能够跟文本串的末位匹配
                        dp[i][j] = dp[i][j - 2];     // *只能匹配0次
                    }
                }
            }
        }
        return dp[cs.length][cp.length];
    }
}

背包问题选编

https://mp.weixin.qq.com/s/xmgK7SrTnFIM3Owpk-emmg

0-1背包模板

dp[N] [C+1] 解法

class Solution {
    public int maxValue(int N, int C, int[] weight, int[] value) {
        int[][] dp = new int[N][C+1];
        // 先处理「考虑第一件物品」的情况
        for (int i = 0; i <= C; i++) {
            dp[0][i] = i >= weight[0] ? value[0] : 0;
        }
        // 再处理「考虑其余物品」的情况
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < C + 1; j++) {
                // 不选该物品
                int n = dp[i-1][j]; 
                // 选择该物品，前提「剩余容量」大于等于「物品体积」
                int y = j >= weight[i] ? dp[i-1][j-weight[i]] + value[i] : 0; 
                dp[i][j] = Math.max(n, y);
            }
        }
        return dp[N-1][C];
    }
}

dp[2] [C+1] 解法

滚动数组优化
根据「转移方程」，我们知道计算第 i 行格子只需要第i-1行中的某些值。
也就是计算「某一行」的时候只需要依赖「前一行」。
因此可以用一个只有两行的数组来存储中间结果，根据当前计算的行号是偶数还是奇数来交替使用第 0 行和第 1 行

class Solution {
    public int maxValue(int N, int C, int[] weight, int[] value) {
        int[][] dp = new int[2][C+1];
        // 先处理「考虑第一件物品」的情况
        for (int i = 0; i < C + 1; i++) {
            dp[0][i] = i >= weight[0] ? weight[0] : 0;
        }
        // 再处理「考虑其余物品」的情况
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < C + 1; j++) {
                // 不选该物品
                int n = dp[(i-1)&1][j]; 
                // 选择该物品
                int y = j >= weight[i] ? dp[(i-1)&1][j-weight[i]] + value[i] : 0;
                dp[i&1][j] = Math.max(n, y);
            }
        }
        return dp[(N-1)&1][C];
    }
}

dp[C+1] 解法

不难发现当求解第i 行格子的值时，不仅是只依赖第i-1 行，还明确只依赖第i-1 行的第c 个格子和第c-weight[i] 个格子（也就是对应着第i 个物品不选和选的两种情况）。
换句话说，只依赖于「上一个格子的位置」以及「上一个格子的左边位置」。
dp数组可以只保留代表「剩余容量」的维度

class Solution {
    public int maxValue(int N, int C, int[] weight, int[] value) {
        int[] dp = new int[C + 1];
        for (int i = 0; i < N; i++) {
            for (int j = C; j >= weight[i]; j--) {	//若当前物品的i的weight大于当前容量C，则无需考虑
                // 不选该物品
                int n = dp[j];	//此时dp[j]相当于dp[i-1][j]
                // 选择该物品	由于是从右往左更新，此时左侧的dp仍然是上一行的结果
                int y = dp[j-weight[i]] + value[i];	//此时dp[j-weight[i]]相当于dp[i-1][j-weight[i]]
                dp[j] = Math.max(n, y);
            }
        }
        return dp[C];
    }
}

416. Partition Equal Subset Sum

public boolean canPartition(int[] nums) {
    int n=nums.length;
    int sum=0;
    for (int i = 0; i < n; i++) {
        sum+=nums[i];
    }
    if((sum&1)==1){
        return false;
    }
    int target=sum/2;
    boolean[] dp=new boolean[target+1];
    dp[0]=true;
    for (int i = 0; i < n; i++) {
        for (int j = target; j >= nums[i]; j--) {
            boolean not_choose=dp[j];
            boolean choose=dp[j-nums[i]];
            dp[j]=not_choose || choose;
        }
    }
    return dp[target];
}

public boolean canPartition(int[] nums) {
    int sum=0;
    int n=nums.length;
    for (int num : nums) {
        sum+=num;
    }
    if(sum%2==1){
        return false;
    }
    int target=sum/2;
    boolean[][] dp=new boolean[n][target+1];
    dp[0][0]=true;
    if(nums[0]<=target){
        dp[0][nums[0]]=true;
    }
    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= target; j++) {
            boolean not_choose=dp[i-1][j];
            boolean choose= j-nums[i]>=0 ? dp[i-1][j-nums[i]] : false;
            dp[i][j]=not_choose || choose;
        }
    }
    return dp[n-1][target];
}

1049. Last Stone Weight II

the smallest possible weight of the left stone

尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了

https://leetcode.cn/problems/last-stone-weight-ii/solution/gong-shui-san-xie-xiang-jie-wei-he-neng-jgxik/

所谓不断「合并」&「重放」，本质只是在构造一个折叠的计算表达式，最终的结果仍然可以使用「为原来 stones 数组中的数字添加 +/− 符号，形成的“计算表达式”」所表示。

问题转换为：为 stones中的每个数字添加 +/−，使得形成的「计算表达式」结果绝对值最小。

从 stones数组中选择，凑成总和不超过
$$
\frac{sum}{2}
$$
的最大价值。

public class LeetCode1049 {
    public int lastStoneWeightII(int[] stones) {
        int sum=0;
        int n=stones.length;
        for (int i = 0; i < n; i++) {
            sum+=stones[i];
        }
        int target=sum/2;
        int[] dp=new int[target+1];
        for (int i = 0; i < n; i++) {
            for (int j = target; j >=stones[i]; j--) {
                int not_choose=dp[j];
                int choose=dp[j-stones[i]]+stones[i];
                dp[j]=Math.max(not_choose,choose);
            }
        }
        return sum-dp[target]*2;
    }
}

474. Ones and Zeroes

public int findMaxForm(String[] strs, int m, int n) {
   int[][] dp=new int[m+1][n+1];
    for (String s : strs) {
        int zeros=count0(s);
        int ones=s.length()-zeros;
        for (int i = m; i >= zeros; i--) {
            for (int j = n; j >= ones; j--) {
                int choose=dp[i-zeros][j-ones]+1;
                int not_choose=dp[i][j];
                dp[i][j]=Math.max(dp[i][j],Math.max(choose,not_choose));
            }
        }
    }
   return dp[m][n];
}

int count0(String s){
    int count=0;
    for (int i = 0; i < s.length(); i++) {
        if(s.charAt(i)=='0'){
            count++;
        }
    }
    return count;
}

494. Target Sum

//a+b=sum
//a-b=target
//a=(sum+target)/2
public int findTargetSumWays(int[] nums, int target) {
    int sum=0;
    for(int num : nums){
        sum+=num;
    }
    if((sum+target)%2==1){
        return 0;
    }
    int k=(sum+target)/2;
    if(k<0){
        return 0;
    }
    int[] dp=new int[k+1];
    dp[0]=1;
    int n=nums.length;
    for(int i=0; i<n; i++){
        for(int j=k; j>=nums[i]; j--){
            dp[j]+=dp[j-nums[i]];
        }
    }
    return dp[k];
}

完全背包模板

dp[N] [C+1] 解法

class Solution {
    public int maxValue(int N, int C, int[] v, int[] w) {
        int[][] dp = new int[N][C + 1];
        
        // 先预处理第一件物品
        for (int j = 0; j <= C; j++) {
            // 显然当只有一件物品的时候，在容量允许的情况下，能选多少件就选多少件
            int maxK = j / v[0];
            dp[0][j] = maxK * w[0];
        }
        
        // 处理剩余物品
        for (int i = 1; i < N; i++) {
            for (int j = 0; j <= C; j++) {
                // 不考虑第 i 件物品的情况（选择 0 件物品 i）
                int n = dp[i - 1][j];
                // 考虑第 i 件物品的情况
                int y = 0;
                for (int k = 1 ;; k++) {
                    if (j < v[i] * k) {
                        break;
                    }
                    y = Math.max(y, dp[i - 1][j - k * v[i]] + k * w[i]);
                }
                dp[i][j] = Math.max(n, y);
            }
        }
        return dp[N - 1][C];
    }
}

dp[2] [C+1] 解法

滚动数组优化
根据「转移方程」，我们知道计算第 i 行格子只需要第i-1行中的某些值。
也就是计算「某一行」的时候只需要依赖「前一行」。
因此可以用一个只有两行的数组来存储中间结果，根据当前计算的行号是偶数还是奇数来交替使用第 0 行和第 1 行

class Solution {
    public int maxValue(int N, int C, int[] v, int[] w) {
        int[][] dp = new int[2][C + 1];
        
        // 先预处理第一件物品
        for (int j = 0; j <= C; j++) {
            // 显然当我们只有一件物品的时候，在容量允许的情况下，能选多少件就选多少件
            int maxK = j / v[0];
            dp[0][j] = maxK * w[0];
        }
        
        // 处理剩余物品
        for (int i = 1; i < N; i++) {
            for (int j = 0; j <= C; j++) {
                // 不考虑第 i 件物品的情况（选择 0 件物品 i）
                int n = dp[(i - 1)&1][j];
                // 考虑第 i 件物品的情况
                int y = 0;
                for (int k = 1 ;; k++) {
                    if (j < v[i] * k) {
                        break;
                    }
                    y = Math.max(y, dp[(i - 1)&1][j - k * v[i]] + k * w[i]);
                }
                dp[i&1][j] = Math.max(n, y);
            }
        }
        return dp[(N - 1)&1][C];
    }
}

dp[C+1] 解法

不难发现当求解第i 行格子的值时，不仅是只依赖第i-1 行，还明确只依赖第i-1 行的第c 个格子和第c-weight[i] 个格子（也就是对应着第i 个物品不选和选的两种情况）。
换句话说，只依赖于「上一个格子的位置」以及「上一个格子的左边位置」。
dp数组可以只保留代表「剩余容量」的维度

class Solution {
    public int maxValue(int N, int C, int[] v, int[] w) {
        int[] dp = new int[C + 1];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j <= C; j++) {
                // 不考虑第 i 件物品的情况（选择 0 件物品 i）
                int n = dp[j];
                // 考虑第 i 件物品的情况
                int y = j - v[i] >= 0 ? dp[j - v[i]] + w[i] : 0; 
                dp[j] = Math.max(n, y);
            }
        }
        return dp[C];
    }
}

279. Perfect Squares

public class LeetCode279 {
    public int numSquares(int n) {
        int[] dp=new int[n+1];
        Arrays.fill(dp,6666);
        dp[0]=0;
        for (int i = 1; i <= n; i++) {
            for(int j=1; j*j<=i; j++){
                int s=j*j;
                dp[i]=Math.min(dp[i],dp[i-s]+1);
            }
        }
        return dp[n];
    }
}

Subarray选编

718. Maximum Length of Repeated Subarray

类似maximum subarray sum，随时比较并更新res

public class LeetCode718 {
    public int findLength(int[] nums1, int[] nums2) {
        int n1=nums1.length;
        int n2=nums2.length;
        int res=0;
        int[][] dp=new int[n1+1][n2+1];
        for (int i = n1-1; i >= 0; i--) {
            for (int j = n2-1; j >= 0; j--) {
                if(nums1[i]==nums2[j]){
                    dp[i][j]=1+dp[i+1][j+1];
                }
                res=Math.max(res,dp[i][j]);
            }

        }
        return res;
    }
}

代码随想录

1035. Uncrossed Lines

有意思的题:

直线不能相交，这就是说明在字符串A中找到一个与字符串B相同的子序列，且这个子序列不能改变相对顺序，只要相对顺序不改变，链接相同数字的直线就不会相交。

precisely the same as longest common subsequence!

public class LeetCode1035 {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int n1=nums1.length;
        int n2=nums2.length;
        int[][] dp=new int[n1+1][n2+1]; //[0,i-1]  [0,j-1]
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if(nums1[i-1]==nums2[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[n1][n2];
    }
}

115. Distinct Subsequences

backtracking果不其然超时，配得上hard题

若要求返回所有结果，则只能backtracking硬干;但注意到本题只要求返回结果数，考虑用dp优化

public class LeetCode115 {
    int res=0;
    public int numDistinct(String s, String t) {
        backtracking(s,t,new StringBuilder(),0);
        return res;
    }

    void backtracking(String s, String t, StringBuilder sb, int i){
        if(sb.length()==t.length() || i==s.length()){
            if(sb.length()==t.length()){
                if(sb.toString().equals(t)){
                    res++;
                }
            }
            return;
        }
        for (int j = i; j < s.length(); j++) {
            sb.append(s.charAt(j));
            backtracking(s,t,sb,j+1);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}

public int numDistinct(String s, String t) {
    int n1=s.length();
    int n2=t.length();
    int[][] dp=new int[n1+1][n2+1]; //s[i:]和t[j:]匹配子序列数
    for (int i = 0; i <= n1; i++) {
        dp[i][n2]=1;    //空序列是任何序列的子序列
    }
    for (int i = n1-1; i >= 0; i--) {
        for (int j = n2-1; j >= 0; j--) {
            if(s.charAt(i)==t.charAt(j)){//只有元素相等才可能派上用场
                dp[i][j]=dp[i+1][j+1]+dp[i+1][j];
            }else{
                dp[i][j]=dp[i+1][j];
            }
        }
    }
    return dp[0][0];
}

自选

120. Triangle

public int minimumTotal(List<List<Integer>> triangle) {
    //dp[i][j]=Math.min(dp[i+1][j],dp[i+1][j+1])+dp[i][j]
    int n=triangle.size();
    int[][] dp=new int[n][n];
    for (int i = n-1; i >= 0; i--) {
        List<Integer> list=triangle.get(i);
        for (int j = 0; j <= i; j++) {
            if(i==n-1){
                dp[i][j]=list.get(j);
            }else{
                dp[i][j]=list.get(j)+Math.min(dp[i+1][j],dp[i+1][j+1]);
            }
        }
    }
    return dp[0][0];
}

Follow up: Could you do this using only O(n) extra space, where n is the total number of rows in the triangle?

public int minimumTotal(List<List<Integer>> triangle) {
    //dp[i][j]=Math.min(dp[i+1][j],dp[i+1][j+1])+dp[i][j]
    int n=triangle.size();
    int[] dp=new int[n];
    for (int i = n-1; i >= 0; i--) {
        List<Integer> list=triangle.get(i);
        for (int j = 0; j <= i; j++) {
            if(i==n-1){
                dp[j]=list.get(j);
            }else{
                dp[j]=list.get(j)+Math.min(dp[j],dp[j+1]);
            }
        }
    }
    return dp[0];
}

256. Paint House

public int minCost(int[][] costs) {
    int n= costs.length;
    int[][] dp=new int[n][3];
    dp[0][0]=costs[0][0];
    dp[0][1]=costs[0][1];
    dp[0][2]=costs[0][2];
    for (int i = 1; i < n; i++) {
        for (int c = 0; c < 3; c++) {
            int min=0;
            if(c==0){
                min=Math.min(dp[i-1][1],dp[i-1][2]);
            }else if(c==1){
                min=Math.min(dp[i-1][0],dp[i-1][2]);
            }else{
                min=Math.min(dp[i-1][0],dp[i-1][1]);
            }
            dp[i][c]=costs[i][c]+min;
        }
    }
    int res=Integer.MAX_VALUE;
    for (int i = 0; i < 3; i++) {
        res=Math.min(res,dp[n-1][i]);
    }
    return res;
}

518. Coin Change II

https://leetcode.com/problems/coin-change-ii/discuss/99212/Knapsack-problem-Java-solution-with-thinking-process-O(nm)-Time-and-O(m)-Space

public int change(int amount, int[] coins) {
    int[][] dp = new int[coins.length+1][amount+1];
    dp[0][0] = 1;
    
    for (int i = 1; i <= coins.length; i++) {
        dp[i][0] = 1;
        for (int j = 1; j <= amount; j++) {
            dp[i][j] = dp[i-1][j] + (j >= coins[i-1] ? dp[i][j-coins[i-1]] : 0);
        }
    }
    return dp[coins.length][amount];
}

for each coin:

not use it
use it

public int change(int amount, int[] coins) {
    int n=coins.length;
    int[] dp=new int[amount+1];

    dp[0]=1;
    for (int coin : coins) {
        for (int i = coin; i <= amount; i++) {
            dp[i]+=dp[i-coin];
        }
    }
    return dp[amount];
}

486. Predict the Winner

好题！

注意：

recurison的返回值不同：
1. 由于recursion函数返回值代表player 1与player 2的最大差值，在player 1的轮次与player 2的轮次，目标是不同的
2. 轮到player 1时，应该尽可能最大化分数
3. 轮到player 2时，应该尽可能最小化分数

Approach #1 Using Recursion [Accepted]

This is done because, looking from Player 1’s perspective, for any move made by Player 1, it tends to leave the remaining subarray in a situation which minimizes the best score possible for Player 2, even if it plays in the best possible manner. But, when the turn passes to Player 1 again, for Player 1 to win, the remaining subarray should be left in a state such that the score obtained from this subarrray is maximum(for Player 1).

This is a general criteria for any arbitrary two player game and is commonly known as the Min-Max algorithm.

public boolean PredictTheWinner(int[] nums) {
    return winner(nums, 0, nums.length - 1, 1) >= 0;
}
public int winner(int[] nums, int s, int e, int turn) {
    //when turn==1, player 1's round
    //when turn==-1, palyer 2's round
    if (s == e)
        return turn * nums[s];
    int a = turn * nums[s] + winner(nums, s + 1, e, -turn);
    int b = turn * nums[e] + winner(nums, s, e - 1, -turn);
    return turn * Math.max(turn * a, turn * b);
    //max(a,b) for 1 and min(a,b) for -1
}

Approach #2 Similar Approach [Accepted]

class Solution {
public:
    //c++ 2-d array difficult to handle, use 2-d vector instead
    vector<vector<int>> dp;
    bool predictTheWinner(vector<int>& nums) {
        int n=nums.size();
        //vector(size,default value)
        dp=vector<vector<int>>(n,vector<int>(n,-1));
        
        return dfs(nums,0,n-1)>=0;
    }
    
    int dfs(vector<int>& nums, int i, int j){
        if(i==j){
            return nums[i];
        }
        if(dp[i][j]!=-1){
            return dp[i][j];
        }
        int a=nums[i]-dfs(nums,i+1,j);
        int b=nums[j]-dfs(nums,i,j-1);
        dp[i][j]=max(a,b);
        return dp[i][j];
        
    }
};

Approach #3 Dynamic Programming [Accepted]:

public boolean PredictTheWinner(int[] nums) {
    int n=nums.length;
    int[][] dp=new int[n][n];
    //a=nums[s]-dp[s+1][e]
    //b=nums[e]-dp[s][e-1]
    for (int i = n-1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            if(i==j){
                dp[i][j]=nums[i];
            }else{
                int a=nums[i]-dp[i+1][j];
                int b=nums[j]-dp[i][j-1];
                dp[i][j]=Math.max(a,b);
            }
        }
    }

    return dp[0][n-1]>=0;
}

2420. Find All Good Indices

转化新题为旧题！

longest non-increasing subarray

longest non-decreasing subarray

public List<Integer> goodIndices(int[] nums, int k) {
    int n=nums.length;
    int[] dp1=new int[n];   //non-increasing order on the left
    int[] dp2=new int[n];   //non-decreasing order on the right
    dp1[0]=1;
    for (int i = 1; i < n; i++) {
        dp1[i]= nums[i]<=nums[i-1] ? dp1[i-1]+1 : 1;
    }
    dp2[n-1]=1;
    for (int i = n-2; i >= 0; i--) {
        dp2[i]= nums[i]<=nums[i+1] ? dp2[i+1]+1 : 1;
    }
    List<Integer> res=new ArrayList<>();
    for (int i = k; i < n-k; i++) {
        if(dp1[i-1]>=k && dp2[i+1]>=k){
            res.add(i);
        }
    }
    return res;
}

IVN

动态规划(2)