[LeetCode][Java] Unique Paths

题目：

A robot is located at the top-left corner of amxngrid (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*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];}}

无论何时何地，只要创造就有收获，只有不息的奋进，才能证明生命的存在。