Untitled

mail@pastecode.io avatar
unknown
java
3 years ago
495 B
3
Indexable
Never
class Solution {
    public int uniquePaths(int m, int n) {
        if (n == 1 || m == 1) return 1;
        
        int[] paths = new int[n];
        for (int i=0; i<n; i++) {
            paths[i] = 1;
        }
        
        for (int i=1; i<m; i++) {
            for (int j=1; j<n; j++) {
                // new value is paths to get to cell above + paths to get to cell to the left
                paths[j] += paths[j-1];
            }
        }
        
        return paths[n-1];
    }
}