97. 交错字符串

leetcode题目链接：https://leetcode.cn/problems/interleaving-string/

leetcode AC记录：

思路：话不多说，动态规划。使用dp[i][j]表示s1从下标0开始，长度为i的子串，和s2从下标0开始，长度为j的子串，能否构成下标从0开始，长度为i+j的子串。状态转移方程为dp[i][j] = (dp[i-1][j] && s1.charAt(i-1) == s3.charAt(i+j-1)) || (dp[i][j-1] && s2.charAt(j-1) == s3.charAt(i+j-1))。

代码如下：

public boolean isInterleave(String s1, String s2, String s3) {boolean[][] dp = new boolean[s1.length()+1][s2.length()+1];if(s2.length() + s1.length() != s3.length()) {return false;}//dp[i][j]表示s1从下标0开始，长度为i的子串，和s2从下标0开始，长度为j的子串，能否构成下标从0开始，长度为i+j的子串//状态转移方程为dp[i][j] = (dp[i-1][j] && s1.charAt(i-1) == s3.charAt(i+j-1)) || (dp[i][j-1] && s2.charAt(j-1) == s3.charAt(i+j-1))dp[0][0] = true;for(int i = 0;i <= s1.length();i++) {for(int j = 0;j <= s2.length();j++) {if(i > 0 && j > 0) {dp[i][j] = (dp[i-1][j] && s1.charAt(i-1) == s3.charAt(i+j-1)) || (dp[i][j-1] && s2.charAt(j-1) == s3.charAt(i+j-1));} else if(i > 0) {dp[i][j] = dp[i-1][j] && s1.charAt(i-1) == s3.charAt(i+j-1);} else if(j > 0) {dp[i][j] = dp[i][j-1] && s2.charAt(j-1) == s3.charAt(i+j-1);}}}return dp[s1.length()][s2.length()];}

 221. 最大正方形

leetcode题目链接：https://leetcode.cn/problems/maximal-square/

leetcode AC记录：

思路：最大正方形，使用dp[i][j]表示以i，j为正方形右下角顶点的最大边长。状态转移方程为dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])。初始化边缘，即i=0,j=[0-length]和i=[0-length][0]为如果[i][j]为1，则面积为1，否则为0。中间使用结果记录最大边长，最后结果是边长的乘积。

代码如下：

public int maximalSquare(char[][] matrix) {//使用dp[i][j]表示以i，j为正方形右下角的最大正方形面积//dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1int[][] dp = new int[matrix.length][matrix[0].length];int res = 0;//初始化dp数组for(int i = 0;i < matrix.length;i++) {if(matrix[i][0] == '1') {dp[i][0] = 1;res = 1;}}for(int i = 0;i < matrix[0].length;i++) {if(matrix[0][i] == '1') {dp[0][i] = 1;res = 1;}}for(int i = 1;i < matrix.length;i++) {for(int j = 1; j < matrix[0].length;j++) {if(matrix[i][j] == '1') {
dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i][j-1], dp[i-1][j])) + 1;}if(res < dp[i][j]) {res = dp[i][j];}}}return res * res;}