动态规划算法-蒲公英云

动态规划算法

1、最长公共子序列

定义网格：以s[i]和s[j]作为结尾的子字符串的最长子序列长度

定义公式：

s[i][j] = s[i - 1][j - 1] + 1 s[i] == s[j] 需要加入公共子序列，长度+1

s[i][j] = ma(s[i - 1][j], s[i][j - 1]), s[i] != s[j],长度保持之前的

private static int longestCommonSubSequence(String s1, String s2){
        int[][] dp = new int[s1.length() + 1][s2.length() + 1];
        for (int i = 0; i < s1.length(); i ++){
            for (int j = 0; j < s2.length(); j ++){
                if (s1.charAt(i) == s2.charAt(j)){
                    dp[i + 1][j + 1] = dp[i][j]  + 1;
                }else {
                    dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]);
                }
            }
        }
        return dp[s1.length()][s2.length()];
    }

2、最长公共子串

定义网格：以s[i]和s[j]作为公共子串结尾的子串长度

定义公式：

s[i][j] = s[i - 1][j - 1] + 1; 如果s[i] == s[j]

s[i][j] = 0; 如果s[i] != s[j]

private static int longestCommonSubstring(String s1 , String s2){
        int[][] dp = new int[s1.length() + 1][s2.length() + 1];
        int maxLength = 0;
        for (int i = 0; i < s1.length(); i ++){
            for(int j = 0; j < s2.length(); j ++){
                if(s1.charAt(i) == s2.charAt(j)){
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                    if (dp[i + 1][j + 1] > maxLength){
                        maxLength = dp[i + 1][j + 1];
                    }
                }else {
                    dp[i + 1][j + 1] = 0;
                }
            }
        }
        return maxLength;
    }

4、最短编辑问题

给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

示例 1:
输入: word1 = "horse", word2 = "ros"
输出: 3
解释: 
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
示例 2:
输入: word1 = "intention", word2 = "execution"
输出: 5
解释: 
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')
定义网格

网格标示s[i] 编辑为s[j] 的最短距离

设计公式

s[i][j] = s[i -1][j - 1] 当s[i] = s[j]时

s[i][j] = min(s[i -1][j - 1], s[i - 1][j], s[i][j - 1]) 当s[i] != s[j]时

public static int minDistance(String word1, String word2) {
        int[][] distance = new int[word1.length() + 1][word2.length() + 1];
        //初始化边界
        for(int i = 0; i < word1.length(); i ++){
            distance[i + 1][0] = i + 1;
        }
        //初始化边界
        for(int j = 0; j < word2.length(); j ++){
            distance[0][j + 1] = j + 1;
        }
        for(int i = 0; i < word1.length(); i ++){
            for(int j = 0; j < word2.length(); j ++){
                if(word1.charAt(i) == word2.charAt(j)){
                    distance[i + 1][j + 1] = distance[i][j];
                }else{
                    distance[i + 1][j + 1] = Math.min(Math.min(distance[i][j], distance[i + 1][j]), distance[i][j + 1]) + 1;
                }
            }
        }
        return distance[word1.length()][word2.length()];
    }