我是比较爱用自底向上的自底向上方法不会计算多余情况， 也不用memo存储

不同路径（062）

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

• 分析

对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 

• 分析

同样是初始化， 再合流

根据dp数组的依赖关系， 可以进行空间优化

最长回文子串（005）

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

    private String longestSubPalindrome(int lef, int rig, String s){
        while (0

• 分析

想到扩散是比较自然的，时间复杂度也不高

最长公共子序列（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 

• 分析

可以看作有两个指针， 匹配的话两个指针一起右移， 不匹配移动其中一个指针找到新的匹配

编辑距离（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 

• 分析

跟上题差不多，不匹配时多了一个情况变为