leetcode/uniquepath.java at master · mapan/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
public class Solution {
    public int uniquePaths(int m, int n) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(m<=0||n<=0) return 0;
        if(m==1&&n==1) return 1;
        return uniquePaths(m-1,n)+uniquePaths(m,n-1);
    }
}

public class Solution {
    int[][] num;
    public int uniquePaths(int m, int n) {
        // Start typing your Java solution below
        // DO NOT write main() function
        num=new int[m+1][n+1];
        return u(m,n);
    }
    public int u(int m,int n) {
        if(m<=0||n<=0) return 0;
        if(m==1&&n==1) return 1;
        if(num[m][n]!=0) return num[m][n];
        num[m-1][n]=u(m-1,n);
        num[m][n-1]=u(m,n-1);
        num[m][n]=num[m-1][n]+num[m][n-1];
        return num[m][n];
    }
}

public class Solution {
    public int uniquePaths(int m, int n) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int[][] num=new int[m+1][n+1];
        for(int i=1;i<=m;i++) {
            for(int j=1;j<=n;j++) {
                if(i==1||j==1)
                    num[i][j]=1;
                else
                    num[i][j]=num[i-1][j]+num[i][j-1];
            }
        }
        return num[m][n];
    }
}

public class Solution {
    public int uniquePaths(int m, int n) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(m<n) {
            int temp=m;
            m=n;
            n=temp;
        }
        int[] num=new int[n+1];
        for(int i=1;i<=m;i++) {
            for(int j=1;j<=n;j++) {
                if(i==1||j==1)
                    num[j]=1;
                else
                    num[j]+=num[j-1];
            }
        }
        return num[n];
    }
}

 public int uniquePaths(int m, int n) {
   if (m == 0 || n == 0) return 0;
   int x = Math.max(m, n), y = Math.min(m, n);
   int[] row = new int[y];

   row[0] = 1;

   // fill up the table
   for (int i=0; i<x; ++i) {
     for (int j=1; j<y; ++j) {
       row[j] += row[j-1];
     }
   }

   return row[y-1];
 }

if(m<=0||n<=0||obstacleGrid[m-1][n-1]==1) return 0;


public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int x=obstacleGrid.length,y=obstacleGrid[0].length;
        if (x == 0 || y == 0) return 0;
       //int x = Math.max(m, n), y = Math.min(m, n);
       int[] row = new int[y];

       // fill up the table
       for (int i=0; i<x; ++i) {
         for (int j=0; j<y; ++j) {
            if(obstacleGrid[i][j]==1) row[j]=0;
            else if(i==0&&j==0) row[j]=1;
            else if(j > 0) row[j] += row[j-1];
         }
       }

       return row[y-1];
    }
    }
}