二维网格中往返路径可获得的最大点数求解问题

问题转化 #

往返路径本质等价于从起点(0,0)同时出发两条不重叠的路径到终点(m-1,n-1)——返回路径（左/上移动）反向后就是从终点到起点的右/下移动路径，因此将问题转化为寻找两条无重复节点（仅起点、终点可共享）的路径，使总点数最大。

动态规划设计 #

状态定义

用dp[k][i1][i2]表示走了k步（k = i1 + j1 = i2 + j2，每步仅右/下，步数等于横纵坐标之和）时，第一条路径到达(i1, j1)、第二条路径到达(i2, j2)的最大点数。其中j1 = k - i1，j2 = k - i2，无需额外存储。

状态转移

两条路径的前一步状态有四种可能组合，取其中最大值，再加上当前节点的点数：

• 若(i1,j1)与(i2,j2)为同一节点，仅加一次该节点的点数；
• 若为不同节点，累加两个节点的点数。

四种前状态组合：

1. 两条路径均向下移动：dp[k-1][i1-1][i2-1]
2. 第一条向下、第二条向右：dp[k-1][i1-1][i2]
3. 第一条向右、第二条向下：dp[k-1][i1][i2-1]
4. 两条路径均向右移动：dp[k-1][i1][i2]

空间优化

由于k步的状态仅依赖k-1步，可将三维数组简化为二维数组dp[i1][i2]，用临时数组存储当前步状态，避免覆盖上一步数据，空间复杂度降至O(m²)，适配m、n=1000的规模。

伪代码实现 #

def max_roundtrip_points(grid, m, n):
    # 初始化DP数组，初始值设为负无穷表示不可达
    dp = [[-float('inf')] * m for _ in range(m)]
    dp[0][0] = grid[0][0]  # 起点初始点数

    total_steps = m + n - 2  # 从起点到终点的总步数
    for k in range(1, total_steps + 1):
        temp = [[-float('inf')] * m for _ in range(m)]
        # 遍历i1的合法范围：j1 = k - i1需在[0, n-1]内
        i1_start = max(0, k - (n - 1))
        i1_end = min(m - 1, k)
        for i1 in range(i1_start, i1_end + 1):
            j1 = k - i1
            if j1 < 0 or j1 >= n:
                continue
            # 遍历i2时从i1开始，利用对称性减少重复计算
            i2_start = i1
            i2_end = min(m - 1, k)
            for i2 in range(i2_start, i2_end + 1):
                j2 = k - i2
                if j2 < 0 or j2 >= n:
                    continue
                
                # 计算当前节点的点数贡献
                current_gain = grid[i1][j1]
                if i1 != i2 or j1 != j2:
                    current_gain += grid[i2][j2]
                
                # 收集所有合法的前状态值
                prev_candidates = []
                if i1 > 0 and i2 > 0:
                    prev_candidates.append(dp[i1-1][i2-1])
                if i1 > 0:
                    prev_candidates.append(dp[i1-1][i2])
                if i2 > 0:
                    prev_candidates.append(dp[i1][i2-1])
                prev_candidates.append(dp[i1][i2])
                
                max_prev = max(prev_candidates)
                if max_prev != -float('inf'):
                    temp[i1][i2] = max_prev + current_gain
        dp = temp
    
    return dp[m-1][m-1]

关键说明 #

• 对称性优化：遍历i2时从i1开始，因为dp[i1][i2]与dp[i2][i1]等价，减少一半计算量；
• 边界处理：仅考虑j1、j2在网格范围内的状态，避免无效计算；
• 去重保证：当两条路径到达同一节点时，仅累加一次点数，确保往返时不会重复获取去程已取过的点。

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