曼哈顿游客

Question

在我的算法和数据结构类中，我被要求使用动态规划实现曼哈顿旅游问题。我已经找到了一种使用动态编程和递归调用相结合的解决方案，但在CodeJudge上进行测试时，我似乎得到了“超过时限”。我还没有弄明白为什么我的代码不够快。有人接电话吗？诚挚的问候。

问题描述:您正在帮助导游公司“曼哈顿游客”，他们正在安排城市导游。他们想在地图上的两点之间找到一条既有趣又短的路。这张地图是方格图。方格图有n行，每行有n个节点。设节点vi，j表示i行上的jth节点，对于1≤I

设vi，j是从s到vi行走时所能得到的最大重量，j在每一步中向下或向右行走。设Di，j是从vi，j降下来的边的重量，让Ri，j是从vi，j直走的边的重量。

在CodeJudge上的描述:在你解决这个问题之前，你必须先阅读、理解和(部分)解决曼哈顿游客在周计划中描述的问题。您的任务是实现您的解决方案。阅读下面的输入/输出规范，并查看示例测试数据，以便学习如何读取输入和写入输出。

输入格式

• 第1行:整数n (1<= n <= 1000)。
• Line 2..n+1: n行R，每个行由n-1个整数隔开；
• Line n+2..2n: n-1行D，每一行由空间分隔的n个整数组成。

输出格式:第1行:最短步行的最大兴趣分数。

到目前为止，我的代码如下：

public static void main(String[] args) {
    Scanner console = new Scanner(System.in);
    int n = console.nextInt();
    
    int[][] R = new int[n][n-1];
    int[][] D = new int[n-1][n];
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n-1; j++) {
            R[i][j] = console.nextInt();
        }
    }
    for(int i = 0; i < n-1; i++) {
        for(int j = 0; j < n; j++) {
            D[i][j] = console.nextInt();
        }
    }
    
    System.out.println(opt(R, D, n, n-1, n-1));
}

public static int opt(int[][]R, int[][]D, int n, int i, int j) {
    int[][] result = new int[n][n];
    
    if(i==0 && j==0) {
        if(result[i][j] == 0) {
            result[i][j] = 0;
        }
        return result[i][j];
        
    } else if(i == 0) {
        if(result[i][j] == 0) {
            result[i][j] = opt(R,D,n,i,j-1) + R[i][j-1];
        }
        return result[i][j];
        
    }else if(j == 0) {
        if(result[i][j] == 0) {
            result[i][j] = opt(R,D,n,i-1,j) + D[i-1][j];
        }
        return result[i][j];
        
    }else if(result[i][j] == 0) {
        result[i][j] = max(opt(R, D, n, i, j-1) + R[i][j-1],opt(R, D, n, i-1, j) + D[i-1][j]);
    }
    
    return result[i][j];
}


public static int max(int i, int j) {
    if(i > j) {
        return i;
    }
    return j;
}

}

Answer 1

为什么是递归？

最上面的行只能水平遍历。因此，对于第一行中的每个顶点，总权重是向左分支的权重之和。您可以在单个循环中计算所有这些参数，作为行中运行的总数。

对于下一行，第一个顶点的总重量是其上方顶点的权重加上它们之间分支的权重。行中每一个下一个顶点的总重量是从上面或从左边的两个可能的最大的一个。

所有这些都可以用两个嵌套循环迭代计算。