leetcode [#62]

目录

• 1. 题目
• 2. 解决方案
• 3. 注意事项

题目

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

Note
m and n will be at most 100.

---

解决方案

public class Solution {
    public int uniquePaths(int m, int n) {
        int[][] map = new int[101][101];
        for(int i = 1; i < 101; i++){
            for(int j = 1; j < 101; j++){
                map[i][j] = 0;
                if(i == 1 || j == 1){
                    map[i][j] = 1;
                } else {
                    int temp = 0;
                    if(map[i][j] == 0){
                        for(int k = 1; k <= i; k++){
                            temp += map[k][j-1];
                        }
                        map[i][j] = temp;
                        map[j][i] = temp;
                    }
                }
            }
        }
        return map[m][n];
    }
}

---

注意事项

1. 找到规律，开辟二维数组，每个位置的值就是m,n为对应下标时不同路线的总数。计算方法是上一行元素从0到i所有元素之和。
2. 这是一道典型的动态规划(DP)题目，上面给出的实质上是暴力递归的方法。而对暴力递归的方法进行优化正是动态规划要做的事情。使用动态规划，就是要考虑当前状态和哪些状态有关，并且只使用这些有意义的状态，避免大量冗余的重复计算。
   在上面的方法中，我们求每个位置的元素时，是将其上一排从0截止到当前横坐标i位置的所有元素进行相加，这就访问了很多次数组。而要想获得这个值，并不是非得需要这样，因为这个“累加过程”我们其实已经做过了—就是在求解当前位置元素左边元素的时候。但是，稍有不同的是，解当前位置元素左边元素的时候，我们求的是从0截止到横坐标i-1位置的所有元素和，差了一个i，而这个正是要求的当前元素上面的元素。因此，找到了规律：求解每个元素，只需要将该元素左边的和上边的元素相加即可。这就减少了大量无意义的计算。代码如下：

   public int uniquePaths(int m, int n) {
       Integer[][] map = new Integer[m][n];
       for(int i = 0; i<m;i++){
           map[i][0] = 1;
       }
       for(int j= 0;j<n;j++){
           map[0][j]=1;
       }
       for(int i = 1;i<m;i++){
           for(int j = 1;j<n;j++){
               map[i][j] = map[i-1][j]+map[i][j-1];
           }
       }
       return map[m-1][n-1];
   }