Unique Paths I leetcode

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?

Unique Paths

• state: f[x][y]从起点到x,y的路径数
• function: (研究倒数第一步)
• f[x][y] = f[x - 1][y] + f[x][y - 1]
• intialize: f[0][0] = 1
• // f[0][i] = 1, f[i][0] = 1//
• 二维数组里面第一行和第一列都为1 因为从起始点到此点的方法只有一种
• answer: f[n-1][m-1]
• 时间是O(m*n) 空间O(m*n)

public class Solution {
    public int uniquePaths(int m, int n) {
        if (m == 0 || n == 0) {
            return 0;
        }
        int [][] sum = new int [m][n];//sum表示从起点到m,n路径数
        for (int i = 0; i < m; i++) {//第一行与第一列因为没有m-1 和 n-1所以都为1
            sum[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            sum[0][j] = 1;
        }
        for (int i = 1; i < m; i++ ) {
            for (int j = 1; j < n; j++){
                sum[i][j] = sum[i-1][j] + sum[i][j-1];
            }
        }
        return sum[m - 1][n - 1];
        
    }
}