Manhattan tourist问题动态规划递归实现超时问题排查求助

• 记忆化完全失效：你在opt递归函数内每次调用都会新建一个result数组，之前计算的所有状态值都会被清空，等于没有做任何缓存，会产生指数级的重复计算，时间复杂度达到O(2^(2n))，n=1000的场景下完全不可能通过。
• 递归方式额外开销大：即使修复了记忆化问题，n=1000的场景下递归深度最高可达2000层，不仅有栈溢出风险，递归调用本身的额外开销也远高于迭代实现。
• 输入读取效率低：Java自带的Scanner对大批量整数输入的读取性能很差，n=1000时需要读取近200万个整数，很容易卡在输入环节。

改用迭代式动态规划实现，直接按顺序计算每个状态的值，时间复杂度稳定为O(n²)，完全满足n=1000的性能要求，同时可以改用BufferedReader加快输入速度。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class ManhattanTourist {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        int[][] R = new int[n][n-1];
        int[][] D = new int[n-1][n];
        
        // 读取R矩阵
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n-1; j++) {
                R[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        // 读取D矩阵
        for (int i = 0; i < n-1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                D[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        // 动态规划数组
        int[][] dp = new int[n][n];
        // 初始化第一行
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j-1] + R[0][j-1];
        }
        // 初始化第一列
        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i-1][0] + D[i-1][0];
        }
        // 递推计算其他状态
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.max(dp[i][j-1] + R[i][j-1], dp[i-1][j] + D[i-1][j]);
            }
        }
        
        System.out.println(dp[n-1][n-1]);
    }
}

内容的提问来源于stack exchange，提问作者moredejlig