面试常考算法题

面试常考算法题(九)-经典动态规划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;i<n;i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]) dp[i]=Math.max(dp[i],dp[j]+1);
            }
        }
        int res=0;
        for(int i=0;i<n;i++){
            res=Math.max(res,dp[i]);
        }
        return res;
    }
}

2.最长公共子序列

"1A2C3D4B56",10,"B1D23CA45B6A",12
返回：6

import 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
返回：4

import 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;
    }
}

4. 最小编辑代价

"abc",3,"adc",3,5,3,100
返回：8

import 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];
	}
}