提问者:小点点

使用动态规划的路径查找问题的时间复杂度


在第一季度给出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];
    }
}

无论是否记忆,如何找到这个问题的时间复杂度?


共1个答案

匿名用户

我发现对于没有mem的递归,它将是O(2^(m n)),但对于mem,它将是O(m*n)。然而,我不是100确定。