力扣150题——多维动态规划
交错字符串
题目
97. 交错字符串 - 力扣（LeetCode）
思路
用dp[i][j]代表s1的前i个字母和s2的前j个字母能否交错组成s3的前i+j-1的子串
状态转移方程即为
- 如果 s1[i-1] == s3[i + j - 1]，并且 dp[i-1][j] 为 true，则 dp[i][j] 也为 true。
- 如果 s2[j-1] == s3[i + j - 1]，并且 dp[i][j-1] 为 true，则 dp[i][j] 也为 true。
代码
public boolean isInterleave(String s1, String s2, String s3) {int n=s1.length(),m=s2.length(),l=s3.length();if(n+m!=l){return false;}boolean[][] dp = new boolean[n+1][m+1];dp[0][0] = true;for(int i=1;i<=n;i++){dp[i][0]=dp[i-1][0]&&s1.charAt(i-1)==s3.charAt(i-1);}for(int i=1;i<=m;i++){dp[0][i]=dp[0][i-1]&&s2.charAt(i-1)==s3.charAt(i-1);}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(dp[i-1][j]&&s1.charAt(i-1)==s3.charAt(i+j-1)){dp[i][j]=true;}else if(dp[i][j-1]&&s2.charAt(j-1)==s3.charAt(i+j-1)){dp[i][j]=true;}}}return dp[n][m];}买卖股票的最佳时机Ⅲ
题目
123. 买卖股票的最佳时机 III - 力扣（LeetCode）
思路
- 设 dp[i][j][0] 表示第 i 天，最多进行 j 次交易，并且当前不持有股票的最大利润。
- 设 dp[i][j][1] 表示第 i 天，最多进行 j 次交易，并且当前持有股票的最大利润。
状态转移方程：
- dp[i][k][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i])
- 即今天不持有股票有两种情况：
- 昨天也不持有股票，或者
- 昨天持有股票，今天卖出股票。
- dp[i][k][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i])
- 即今天持有股票也有两种情况：
- 昨天也持有股票，或者
- 昨天不持有股票，今天买入股票。
代码
public int maxProfit(int[] prices) {int n = prices.length;if(n==0){return 0;}int[][][] dp = new int[n][3][2];for(int i=0;i<3;i++){dp[0][i][0]=0;dp[0][i][1]=-prices[0];}for(int i=1;i<n;i++){for(int j=1;j<3;j++){dp[i][j][0]=Math.max(dp[i-1][j][0],dp[i-1][j][1]+prices[i]);dp[i][j][1]=Math.max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i]);}}return dp[n-1][2][0];}买卖股票的最佳时机Ⅳ
题目
188. 买卖股票的最佳时机 IV - 力扣（LeetCode）
思路
只需要在上一题的基础上讲k的值化为动态的，并且最后遍历所有的K，找出能达到最大利益的K，并返回最大值。
代码
public int maxProfit(int k, int[] prices) {int n = prices.length;if(n==0||k==0){return 0;}int[][][] dp = new int[n][k+1][2];for(int i=0;i<=k;i++){dp[0][i][0]=0;dp[0][i][1]=-prices[0];}for(int i=1;i<n;i++){for(int j=1;j<=k;j++){dp[i][j][0]=Math.max(dp[i-1][j][0],dp[i-1][j][1]+prices[i]);dp[i][j][1]=Math.max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i]);}}int max = Integer.MIN_VALUE;for(int i=0;i<=k;i++){max = Math.max(dp[n-1][i][0],max);}return max;}最大正方形
题目
221. 最大正方形 - 力扣（LeetCode）
思路
dp[i][j]表示以位置(i, j)作为正方形右下角的最大正方形的边长。- 若 matrix[i][j] == '1'，则 dp[i][j] 的值由 dp[i-1][j]（上）、dp[i][j-1]（左）和 dp[i-1][j-1]（左上）的最小值加1决定。
代码
public int maximalSquare(char[][] matrix) {int n = matrix.length;if(n==0){return 0;}int m = matrix[0].length;int[][] dp = new int[n][m];int max = Integer.MIN_VALUE;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;}else{dp[i][j]=Math.min(dp[i-1][j],Math.min(dp[i-1][j-1],dp[i][j-1]))+1;}max = Math.max(max,dp[i][j]);}}}return max*max;}