[LeetCode][Java] Unique Paths

[LeetCode][Java] Unique Paths

題目：

 

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?

Above is a 3 x 7 grid. How many possible unique paths are there?

題意：

給定一個m x n的網格結構，一個機器人從網格的左上角移動到右下角，每次只能向右或者向下移動一格，問一共有多少種移動方式。

算法分析：

* 動態規劃：
*
* 具體而言，定義m*n維二維數組dp[][],dp[i][j]表示從s出發到達格子(i,j)的路徑數目， * 現在我們可以思考如果寫dp方程。通過觀察網格特征和走法，我們可以分析得知，到達（i,j）只有兩種走法， * 第一是從（i-1,j）向下到(i,j)，第二是從（i,j-1）向右到（i,j），而dp[i][j-1]和dp[i-1][j]是已經保存的中間計算結果， * 所以可以得到dp遞推方程為dp[i][j] = dp[i][j-1] + dp[i-1][j]。所以可以從(0,0)開始不斷計算到右側和下方的格子的路徑總數， * 直到算出dp[m-1][n-1]，算法時間復雜度為O（mn），空間復雜度也為O（mn）。
*

算法如下：

public class Solution 
{
    public int uniquePaths(int m, int n) 
    {
        //dp[i][j] = dp[i-1][j] + dp[i][j-1];
        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];
    }
}