Leetcode_62_UniquePaths_唯一路径数

这个是Leetcode上的第62个题目，属于动态规划DynamicProgramming的Medium题目。
后来才发现完美世界的一道算法题就是根据这个题目改造的，有兴趣的同学可以看下这道题目：
https://www.nowcoder.com/discuss/173242?type=0&order=0&pos=17&page=1

/*JianzhiOffer_62_UniquePaths_唯一路径数/
/**
* JianzhiOffer_62_UniquePaths_唯一路径数
* 题目介绍:
* 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?
* <p>
* start 0 0 0 0 0 0
* 0 0 0 0 0 0 0
* 0 0 0 0 0 0 finish
* Above is a 7 x 3 grid. How many possible unique paths are there?
* Note: m and n will be at most 100.
* <p>
* Example 1:
* Input: m = 3, n = 2
* Output: 3
* Explanation:
* From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
* 1. Right -> Right -> Down
* 2. Right -> Down -> Right
* 3. Down -> Right -> Right
* Example 2:
* Input: m = 7, n = 3
* Output: 28
* <p>
*
* 解题思路：动态规划。
* 从finish终点倒着推向start点。
* dp[][]数组的每一个元素表示当前该点作为start点到finish点的路径数。
* 初始化：
* dp[rows - 1][i] = 1;
* dp[i][cols - 1] = 1;
* 动态规划表达式:
* dp[i][j] = dp[i][j + 1] + dp[i + 1][j];
* 最终返回dp[0][0]即可。
*/
public int uniquePaths(int cols, int rows) {
if (cols < 1 || rows < 1) return 0;
if (cols == 1 || rows == 1) return 1;
int[][] dp = new int[rows][cols];
//init
for (int i = 0; i < cols - 1; i++) dp[rows - 1][i] = 1;//最后一行初始化
for (int i = 0; i < rows - 1; i++) dp[i][cols - 1] = 1;//最后一列初始化
for (int i = rows - 2; i >= 0; i--) {
for (int j = cols - 2; j >= 0; j--) {
dp[i][j] = dp[i][j + 1] + dp[i + 1][j];
}
}
return dp[0][0];
}