在第一季度给出x, y坐标,你尝试到达原点(0,0),例如,如果你在点(1,1),你可以到达点1,0,然后是0,0。返回您可以选择的唯一路径数。您只能向左或向下移动。
这可以递归地解决,并且通过记忆,您可以优化解决方案。
class Solution {
public static int findUniquePaths(int x, int y){
if(x == 0 || y == 0 ){
return 1;
}
return findUniquePaths(x -1, y) + findUniquePaths(x, y -1);
}
//initialize mem to -1 before calling this function.
public static int findUniquePathsDP(int x, int y,int[][] mem){
if(x == 0 || y == 0 ){
return 1;
}
if (mem[x][y] != -1){
return mem[x][y];
}
mem[x][y] = findUniquePathsDP(x -1, y,mem) + findUniquePathsDP(x, y -1,mem);
return mem[x][y];
}
}
无论是否记忆,如何找到这个问题的时间复杂度?
我发现对于没有mem的递归,它将是O(2^(m n)),但对于mem,它将是O(m*n)。然而,我不是100确定。