首页 > 代码库 > Leetcode: Unique Paths

Leetcode: Unique Paths

2024-07-04 09:50:28   225人阅读

这道题最开始采用recursive的方法，结果犯了TLE(time limit exceeded)的错误，事实证明recursive的时间代价还是太高，所以改用DP的方法，把曾经算出来的结果存起来，我用的是一个M*N的matrix来存储

 1 public class Solution {
 2     public int uniquePaths(int m, int n) {
 3         if (m <= 0 || n <= 0) return 0;
 4         if (m == 1 && n == 1) return 1;
 5         int[][] matrix = new int[m][n];
 6         return findpath(m, n, matrix);
 7     }
 8     
 9     public int findpath(int m, int n, int[][] matrix){
10         if (matrix[m-1][n-1] != 0) return matrix[m-1][n-1];
11         else if (m == 1 && n != 1) {
12             matrix[0][n-1] = 1;
13             return matrix[0][n-1];
14         }
15         else if (m != 1 && n == 1) {
16             matrix[m-1][0] = 1;
17             return matrix[m-1][0];
18         }
19         else matrix[m-1][n-1] = findpath(m-1, n, matrix) + findpath(m, n-1, matrix);
20         return matrix[m-1][n-1];
21     }
22 }

之前的recursive算法：

 1 public class Solution {
 2     public int uniquePaths(int m, int n) {
 3         if (m < 0 || n < 0) return 0;
 4         if (m == 1 && n == 0) return 1;
 5         if (m == 0 && n == 1) return 1;
 6         else if (m == 0 && n != 0) return uniquePaths(0, n-1);
 7         else if (m != 0 && n == 0) return uniquePaths(m-1, 0);
 8         else return uniquePaths(m-1, n) + uniquePaths(m, n-1);
 9     }
10 }

 


联系
我们