Leetcode——62. Unique Paths

題目原址

https://leetcode.com/problems/unique-paths/description/

題目描述

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.

Example1：

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

Example2：

Input: m = 7, n = 3

Output: 28

解題思路

利用動态規劃的思想，動态規劃的關鍵是找到遞推公式。該題：到達某一個點的路徑數等于到達它上一點的陸靜姝與它左邊的路徑數之和。即：起始點到終點

(i，j)

的路徑數 = 起始點到

(i - 1，j)

的路徑數 + 起始點到

(i，j - 1)

的路徑數。

AC代碼

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] ret = new int[m][n];

        for(int i = ; i < m; i++) {
            for(int j = ; j < n; j++) {
                if(i ==  || j == ) ret[i][j] = ;
                else
                    ret[i][j] = ret[i - ][j] + ret[i][j - ];
            }
        }
        return ret[m - ][n - ];       
    }
}