Dynamic planning - 62. Different paths

1 Title Description

A robot is in a m x n The top left corner of the grid （ The starting point is marked as “Start” ）.

The robot can only move down or right one step at a time . The robot tries to reach the bottom right corner of the grid （ In the figure below, it is marked as “Finish” ）.

Ask how many different paths there are in total ？

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/unique-paths

2 Title Example

Example 2：
Input ：m = 3, n = 2
Output ：3
explain ：
From the top left corner , All in all 3 Path to the bottom right .

1. towards the right -> Down -> Down
2. Down -> Down -> towards the right
3. Down -> towards the right -> Down

Example 3：
Input ：m = 7, n = 3
Output ：28

Example 4：
Input ：m = 3, n = 3
Output ：6

3 Topic tips

1 <= m, n <= 100
Question data guarantee that the answer is less than or equal to 2 * 10⁹

4 Ideas

We use it f(i,j) It means walking from the upper left corner to (i,j) Number of paths for , among i and j The scope of each is [0, m) and [0, n).
Because we can only move down or right with each step — Step , So if you want to go to (i,j), If you take a step down , So from (i-1,j) Come over ; If you take a step to the right , So from (i,j-1) Come over . So we can write the dynamic programming transfer equation :

It should be noted that , If i=0, that f(i - 1,j) It is not a state that meets the requirements , We need to ignore this ― term ; Empathy , If j=0, that f(i,j-1) It is not a state that meets the requirements , We need to ignore this — term . The initial condition is f(0,0)= 1, That is, from the upper left corner to the upper left corner — Methods . The final answer is f(m - 1,n - 1).

details :
In order to facilitate code writing , We can put all f(0,j) as well as f(i,0) Are set as boundary conditions , Their values are 1.

Complexity analysis
Time complexity :O(mn).
Spatial complexity :O(mn), That is, the space required to store all States . be aware f(i,j) Only with section i Xing He i-1 The status of the line is related to , Therefore, we can use the rolling array instead of the two-dimensional array in the code , Reduce the space complexity to O(n). Besides , Since we exchange the values of rows and columns, it will not affect the answer , So we can always exchange m and n bring m≤ n, In this way, the spatial complexity is reduced to O(min(m, rn)).

5 My answer

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