Leetcode62:不同路径（动态规划）；Leetcode64:最小路径和（动态规划）

62：

来源：

重点：

　　类似这种只问有多少种方案，而不问具体方案是什么时，常用动态规划。

动态规划，数组dp[m][n]为状态数组，表示到达(m-1,,n-1)点的路径数量

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

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

64：

来源：

 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];
 7 
 8         for(int j = 1;j){
 9             dp[0][j]=grid[0][j]+dp[0][j-1];
10         }
11 
12         for(int i = 1; i){
13             dp[i][0]=grid[i][0]+dp[i-1][0];
14         }
15 
16         for(int i = 1; i){
17             for(int j = 1; j){
18                 dp[i][j] = Math.min(grid[i][j]+dp[i-1][j],grid[i][j]+dp[i][j-1]);
19             }
20         }
21         return dp[m-1][n-1];
22     }
23 }