Blind 75
Unique Paths
- Problem
- LC 62
- Category
- DP
- File
- blind75_LC62UniquePaths.java
- Path
- pkg5leetcode/blind75/blind75_LC62UniquePaths.java
- Package
- pkg5leetcode.blind75
- Command
- java pkg5leetcode/blind75/blind75_LC62UniquePaths.java
- Approach
- Grid DP paths[i][j] = paths[i-1][j] + paths[i][j-1].
- Complexity
- Time O(mn), Space O(n)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.blind75;2 3/*4 * Unique Paths | LC 625 * APPROACH: Grid DP paths[i][j] = paths[i-1][j] + paths[i][j-1].6 * COMPLEXITY: Time O(mn), Space O(n)7 */8public class blind75_LC62UniquePaths {9 static int uniquePaths(int m, int n) {10 int[] row = new int[n];11 java.util.Arrays.fill(row, 1);12 for (int i = 1; i < m; i++)13 for (int j = 1; j < n; j++)14 row[j] += row[j - 1];15 return row[n - 1];16 }17 18 public static void main(String[] args) {19 check(uniquePaths(3, 7) == 28, "case1");20 check(uniquePaths(3, 2) == 3, "case2");21 System.out.println("all tests passed");22 }23 24 static void check(boolean cond, String name) {25 if (!cond) throw new AssertionError("FAILED: " + name);26 System.out.println(" PASS " + name);27 }28}