动态规划相关的例子(动态规划定义)

1.编辑距离2.最长递增子序列3.最大子数组的和4.最长公共子序列5.两个字符串的删除操作6.两个字符串的最小ASCII删除和7.总结

思路：从后往前分别遍历两个字符串，对于每一个i，j位置，考虑把word1变换成word2，所以对于每一个i来说，有三个选择，选择删除，选择插入，选择替换。
dp函数表示为返回 s1[0…i] 和 s2[0…j] 的最小编辑距离。
basecase为i或j走到-1，则把剩下的全部删除或者全部插入

Map map;
    public int minDistance(String word1, String word2) {
        map = new HashMap<>();
        return dp(word1,word2,word1.length()-1,word2.length()-1);
    }

    public int dp(String word1,String word2, int i,int j){
        if (i==-1) return j+1;

        if (j==-1) return i+1;

        String key = i + "-" + j;
        if (map.containsKey(key)){
            return map.get(key);
        }

        if (word1.charAt(i)==word2.charAt(j)) {
            return dp(word1,word2,i-1,j-1);
        }
        else {
            map.put(key,getMin(dp(word1,word2,i,j-1)+1,dp(word1,word2,i-1,j )+1,dp(word1,word2,i-1,j-1)+1));
        }
        return map.get(key);

    }

    public int getMin(int a,int b,int c){
        int min = Math.min(a, b);
        return Math.min(min, c);
    }

思路：dp[i]表示以nums[i]数字结尾的最长递增子序列的长度，则如何求出dp[i+1]呢，只要从i+1个位置往前遍历，找到比nums[i+1]小的哪些nums位置，相应的dp[index]+1即可
这种定义下，最后需要遍历整个dp数组找到最终的解

ublic int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int res = 0;
        Arrays.fill(dp,1);
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] 
3.最大子数组的和 

 思路：动态规划。注意是求连续的最大子数组的和
 定义dp[i]表示以nums[i]结尾的最大子数组的和
 如何表示dp[i+1]?
 dp[i+1]可能为dp[i]+nums[i+1]，表示i+1个位置和前面的子数组相连构成了更长的子数组
 dp[i+1]可能就为dp[i+1]表示不与前面的相连，自成一个子数组，取最大的就行
 
这种定义下，最后需要遍历整个dp数组找到最终的解
 
public static int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE;
        int[] res = new int[nums.length];
        res[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            res[i] = Math.max(nums[i],nums[i]+res[i-1]);
        }
        for (int re : res) {
            if (re>max){
                max = re;
            }
        }
        return max;
    }
 
4.最长公共子序列 

 思路：动态规划
 对于这种给定两个字符串下的问题，一般都是两个指针分别指向字符串然后遍历，定义dp(i,j)函数，考虑s1[i]和s2[j]的字符，如果两个相同，则最长公共子序列长度加1，若不同，则有三种可能，第一种，s1包含在最长公共子序列中，第二种，s2包含在最长公共子序列中，第三种，都不包含。第三种情况包括在1，2中
 
int[][] memo;
    public int longestCommonSubsequence(String text1, String text2) {
        memo = new int[text1.length()][text2.length()];
        for (int[] ints : memo) {
            Arrays.fill(ints,-1);
        }
        return dp(text1,text2,0,0);
    }
    public int dp(String s1, String s2,int i, int j){
        if (i>=s1.length()||j>=s2.length()) return 0;


        if (memo[i][j]!=-1){
            return memo[i][j];
        }

        if (s1.charAt(i)==s2.charAt(j)){
            return dp(s1,s2,i+1,j+1)+1;
        }else{
            memo[i][j] = getMax(dp(s1,s2,i,j+1),
                    dp(s1,s2,i+1,j),
                    dp(s1,s2,i+1,j+1));
            return memo[i][j];
        }
    }

    public int getMax(int a,int b,int c){
        int max = Math.max(a,b);
        return Math.max(max,c);
    }
 
5.两个字符串的删除操作 

 思路：其实和最长公共子序列的问题相同，求出两个字符串的最长公共子序列，然后两个字符串的长度之和，减去2倍的最长公共子序列长度即可
 
int[][] memo;
    public int minDistance(String word1, String word2) {
        memo = new int[word1.length()][word2.length()];
        for (int[] ints : memo) {
            Arrays.fill(ints,-1);
        }
        return word1.length()+word2.length()-2*dp(word1,word2,0,0);
    }

    public int dp(String word1, String word2,int i,int j){
        if (i==word1.length()||j==word2.length()){
            return 0;
        }

        if (memo[i][j]!=-1){
            return memo[i][j];
        }
        if (word1.charAt(i)==word2.charAt(j)){
            return dp(word1,word2,i+1,j+1)+1;
        }else {
            memo[i][j] =  Math.max(dp(word1,word2,i+1,j),
                    dp(word1,word2,i,j+1));
            return memo[i][j];
        }
    }
 
6.两个字符串的最小ASCII删除和 
 
思路：和求最长公共子序列的问题类似，可以类比编辑距离，定义dp(i,j)为
 s1[…i],s2[…j]的最小ascii删除和，则每次可以选择删除s1的i处字符或者s2的j处字符，basecase为i=-1或者j=-1，这个basecase返回的是将另一个字符串剩下的全部删除。
 
int[][] memo;
    public int minimumDeleteSum(String s1, String s2) {
        memo = new int[s1.length()][s2.length()];
        for (int[] ints : memo) {
            Arrays.fill(ints,-1);
        }
        return dp(s1,s2,s1.length()-1,s2.length()-1);
    }

    //dp表示s1[..i]和s2[..j]两个字符串的最小删除和
    public int dp(String s1, String s2,int i,int j){
        int res = 0;
        if (i==-1){
            while (j>=0){
                res+=s2.charAt(j);
                j--;
            }
            return res;
        }
        if (j==-1){
            while (i>=0){
                res+=s1.charAt(i);
                i--;
            }
            return res;
        }
        if (memo[i][j]!=-1){
            return memo[i][j];
        }
        if (s1.charAt(i)==s2.charAt(j)){
            return dp(s1,s2,i-1,j-1);
        }else {
            memo[i][j] =  Math.min(s1.charAt(i)+dp(s1,s2,i-1,j),s2.charAt(j)+dp(s1,s2,i,j-1));
            return memo[i][j];
        }
    }
 
7.总结 
这类题目一般给出两个字符串就有两个指针，dp是一个函数，用递归解决
 给出一个字符串一般就是用一个dp数组去求出每一个位置的最优解，然后最后遍历这个数组求出全局最优解。