hot100之多维动态规划

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

不同路径（062）

1. class Solution {
2.     public int uniquePaths(int m, int n) {
3.         int[][] dp = new int[m][n];
4.         for (int i = 0; i < m;i++){
5.             dp[i][0] = 1;
6.         }
7.         for (int j = 0; j < n; j++){
8.             dp[0][j] = 1;
9.         }
11.         for (int i = 1; i < m; i++){
12.             for (int j = 1; j < n; j++){
13.                 dp[i][j] = dp[i-1][j] + dp[i][j-1];
14.             }
15.         }
17.         return dp[m-1][n-1];
18.     }
19. }

复制代码

• 分析
  

对0行0列初始化，后进行合流
最小路径和（064）

1. class Solution {
2.     public int minPathSum(int[][] grid) {
3.         int m = grid.length;
4.         int n = grid[0].length;
5.         int[][] dp = new int[m][n];
6.         dp[0][0] = grid[0][0];
8.         for (int i = 1; i < m; i++){
9.             dp[i][0] = dp[i-1][0] + grid[i][0];
10.         }
11.         for (int j = 1; j < n; j++){
12.             dp[0][j] = dp[0][j-1] + grid[0][j];
13.         }
15.         for (int i = 1; i < m; i++){
16.             for (int j = 1; j < n; j++){
17.                 dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
18.             }
19.         }
21.         return dp[m-1][n-1];
22.     }
23. }

复制代码

• 分析
  

同样是初始化， 再合流
根据dp数组的依赖关系， 可以进行空间优化
最长回文子串（005）

[code]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