hot100之多维动态规划

hot100中的多维动态规划应用

本人较为偏好采用自底向上的办法，该方法不会计算多余情形，也无需借助memo进行存储

不同路径（062）

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }

        return dp[m-1][n-1];
    }
}

• 分析

对第0行与第0列进行初始化，随后通过双重循环来整合计算路径数量

最小路径和（064）

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];

        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j-1] + grid[0][j]; 
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
            }
        }

        return dp[m-1][n-1];
    }
}

• 分析

同样是先进行初始化操作，之后依据动态规划的依赖关系来整合计算最小路径和，并且提到可以进行空间优化

最长回文子串（005）

class Solution {
    public String longestPalindrome(String s) {
        String res = " ";
        for (int i = 0; i < s.length(); i++) {
            String str1 = longestSubPalindrome(i, i, s);
            String str2 = longestSubPalindrome(i, i+1, s);
            res = res.length() > str1.length() ? res : str1;
            res = res.length() > str2.length() ? res : str2;
        }
        return res;
    }

    private String longestSubPalindrome(int lef, int rig, String s) {
        while (0 <= lef && rig < s.length() && s.charAt(lef) == s.charAt(rig)) {
            lef--;
            rig++;
        }
        return s.substring(lef+1, rig);
    }
}

• 分析

考虑到通过扩散的方式来探寻最长回文子串是比较自然的思路，而且时间复杂度也处于较为可观的水平

最长公共子序列（1143）

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        char[] charArray1 = text1.toCharArray();
        char[] charArray2 = text2.toCharArray();

        int m = charArray1.length;
        int n = charArray2.length;

        int[][] dp = new int[m+1][n+1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (charArray1[i-1] == charArray2[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
                }
            }
        }
        return dp[m][n];
    }
}

• 分析

可看作有两个指针在两个字符串上移动，当字符匹配时两个指针一同右移，不匹配时则移动其中一个指针去寻找新的匹配情况

编辑距离（072）

class Solution {
    public int minDistance(String word1, String word2) {
        char[] charArray1 = word1.toCharArray();
        char[] charArray2 = word2.toCharArray();
        int m = charArray1.length;
        int n = charArray2.length;
        int[][] dp = new int[m+1][n+1];

        for (int i = 0; i < m; i++) {
            dp[i+1][0] = i+1;
        }
        for (int j = 0; j < n; j++) {
            dp[0][j+1] = j+1;
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (charArray1[i-1] == charArray2[j-1]) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1;
                }
            }
        }
        return dp[m][n];
    }
}

• 分析

与上一题有相似之处，在字符不匹配时会出现移动A指针、移动B指针、移动双指针这几种不同的处理情形