方格取数

### 方格取数问题的动态规划算法实现 #### 问题描述 在一个 \( N \times N \) 的方格图中，某些方格填有正整数值，其余为空白（即值为 0）。目标是从左上角 (\(1,1\)) 走到右下角 (\(N,N\))，允许走两次不同的路径，并使这两条路径上的数字总和最大化。每经过一个方格，可以拾起其上的数字。 --- #### 解决思路 此问题可以通过 **二维动态规划** 来解决。由于需要考虑两条不重叠的路径，因此状态设计较为复杂。以下是具体分析： 1. **定义状态变量** 设定四维的状态表示方式： - \( dp[x1][y1][x2][y2] \): 表示第一条路径到达坐标 (\(x1,y1\)) 和第二条路径到达坐标 (\(x2,y2\)) 时的最大得分。 如果两条路径当前位于同一格子，则只累加一次该格子的值；如果不在同一格子，则分别累加对应的值[^3]。 2. **初始化条件** 初始化起点 (\(dp[1][1][1][1]\)) 的初始值为网格中的第一个单元格值 \( grid[1][1] \)[^5]。 3. **转移方程** 对于每一个可能的状态 (\(x1,y1,x2,y2\)): - 假设可以从四个方向之一移动过来：上方或左侧。 - 更新公式如下： ```python if (x1 == x2 and y1 == y2): dp[x1][y1][x2][y2] = max( dp[x1-1][y1][x2-1][y2], # 上一步均为向上 dp[x1-1][y1][x2][y2-1], # 第一条路径向上，第二条向左 dp[x1][y1-1][x2-1][y2], # 第一条路径向左，第二条向上 dp[x1][y1-1][x2][y2-1] # 双方均向左 ) + grid[x1][y1] else: dp[x1][y1][x2][y2] = max( dp[x1-1][y1][x2-1][y2], dp[x1-1][y1][x2][y2-1], dp[x1][y1-1][x2-1][y2], dp[x1][y1-1][x2][y2-1] ) + grid[x1][y1] + grid[x2][y2] ``` 4. **边界处理** 需要特别注意越界情况以及当两条路径相交的情况下的特殊逻辑。 5. **优化空间复杂度** 使用滚动数组技术来减少内存消耗。因为每次更新仅依赖前一时刻的数据，故可将三维数组压缩至两层循环内的二维存储结构[^5]。 6. **最终结果提取** 结果存放在终点处的所有可能性之中最大的那个值里头，也就是遍历所有可能结束位置组合求得最大值作为答案返回给调用者函数。 --- #### Python 实现代码 下面提供了一个基于上述理论框架的具体实现版本： ```python def max_sum_of_two_paths(grid): n = len(grid) # Initialize DP table with zeros. dp = {} # Initial state setup at the start point of both paths being same i.e., top-left corner. dp[(1, 1, 1, 1)] = grid[1][1] directions = [(0,-1), (-1,0)] for sum_steps in range(2, 2*n): new_dp = {} for pos1 in range(max(sum_steps-n+1,1), min(n,sum_steps)+1): pos2 = sum_steps - pos1 if not (1<=pos2<=n): continue for path1_dir in directions: prev_pos1_x = pos1-path1_dir[0] prev_pos1_y = pos2-path1_dir[1] if not (1<=prev_pos1_x<=n and 1<=prev_pos1_y<=n): continue for path2_dir in directions: prev_pos2_x = pos1-path2_dir[0] prev_pos2_y = pos2-path2_dir[1] if not (1<=prev_pos2_x<=n and 1<=prev_pos2_y<=n): continue key_prev = (prev_pos1_x, prev_pos1_y, prev_pos2_x, prev_pos2_y) if key_prev not in dp: continue current_key = (pos1,pos2,min(pos1,pos2),max(pos1,pos2)) value_to_add = ( grid[pos1][pos2] + ((grid[pos1][pos2]) if pos1 != pos2 or pos1==pos2 else 0 ) ) if current_key not in new_dp: new_dp[current_key] = dp[key_prev]+value_to_add else: new_dp[current_key] = max(new_dp[current_key], dp[key_prev]+value_to_add) dp = new_dp result = 0 for k,v in dp.items(): if v>result: result=v return result ``` --- #### 复杂度分析 时间复杂度主要由状态数量决定，大约为 \(O(N^4)\)，但由于实际计算过程中会有很多剪枝操作，通常运行效率较高。空间复杂度则通过滚动数组降低到了 \(O(N^2)\)。 ---