面试常考算法题(九)-经典动态规划1
1.最长递增子序列
[2,1,4,3,1,5,6],7 返回:4
import java.util.*; public class AscentSequence { public int findLongest(int[] nums, int n) { int[]dp=new int[n]; Arrays.fill(dp,1); for(int i=1;inums[j]) dp[i]=Math.max(dp[i],dp[j]+1); } } int res=0; for(int i=0;i 2.最长公共子序列
"1A2C3D4B56",10,"B1D23CA45B6A",12 返回:6import java.util.*; public class LCS { public int findLCS(String a, int m, String b, int n) { int[][] dp=new int[m+1][n+1]; for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ if(a.charAt(i-1)==b.charAt(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]; } }3.最长公共子串
"1AB2345CD",9,"12345EF",7 返回:4import java.util.*; public class LongestSubstring { public int findLongest(String a, int m, String b, int n) { int[][]dp=new int[m+1][n+1]; int res=0; for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ if(a.charAt(i-1)==b.charAt(j-1)){ dp[i][j]=dp[i-1][j-1]+1; if(dp[i][j]>res) res=dp[i][j]; } } } return res; } }
- 最小编辑代价
"abc",3,"adc",3,5,3,100 返回:8import java.util.*; public class MinCost { public int findMinCost(String a, int m, String b, int n, int c0, int c1, int c2) { int[][]dp=new int [m+1][n+1]; for(int j=1;j<=n;j++) dp[0][j]=dp[0][j-1]+c0;//插入 for(int i=1;i<=m;i++) dp[i][0]=dp[i-1][0]+c1;//删除 for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ if(a.charAt(i-1)==b.charAt(j-1)) dp[i][j]=dp[i-1][j-1]; else dp[i][j]=Math.min(Math.min(dp[i-1][j-1]+c2,dp[i-1][j]+c1),dp[i][j-1]+c0);//插入、删除和修改的代价c0,c1,c2 } } return dp[m][n]; } }5.字符串交错组成
"ABC",3,"12C",3,"A12BCC",6 C包含且仅包含A,B中所有字符import java.util.*; public class Mixture { public boolean chkMixture(String A, int m, String B, int m, String C, int v) { if(m + n != v) return false; boolean[][] dp = new boolean[n + 1][m + 1]; dp[0][0] = true;//dp[i][j]表示C[0...i+j-1]能否用A[0...i-1]和B[0...j-1]组成 for (int i = 1; i <= m; i ++) { if(A.charAt(i - 1) == C.charAt(i - 1)) dp[i][0] = true; else break; } for (int j = 1; j <= n; j ++) { if(B.charAt(j - 1) == C.charAt(j - 1)) dp[0][j] = true; else break; } for (int i = 1; i <= m; i ++) { for (int j = 1; j <= n; j ++) { dp[i][j] = (A.charAt(i - 1) == C.charAt(i + j - 1) && dp[i - 1][j]) || (B.charAt(j - 1) == C.charAt(i + j - 1) && dp[i][j - 1]); } } return dp[m][n]; } }