首页/新闻资讯/正文详情

动态规划解决方格取数问题:双人路径最优解

发布时间:2026/11/2 16:45:29 来源:云帆数科 栏目:资讯中心
动态规划解决方格取数问题:双人路径最优解
1. 问题背景与题目解析方格取数是一道经典的动态规划题目最初出现在2000年全国青少年信息学奥林匹克竞赛(NOIP)提高组的比赛中。这道题目考察的是在二维网格中进行路径规划时如何高效计算最优解的能力。题目描述大致如下给定一个N×N的方格矩阵每个格子中有一个正整数。现在有一个人从左上角(1,1)出发每次只能向右或向下移动最终到达右下角(N,N)。在移动过程中经过的格子中的数字会被取走。题目要求计算从起点到终点能够取到的数字之和的最大值。这个问题的经典解法是使用动态规划时间复杂度为O(N²)。但题目还有一个进阶版本如果允许两个人同时从起点出发各自独立移动两人路径可以交叉但不能重复取同一个格子的数字问两人能够取到的数字之和的最大值是多少这就是P1004这道题的核心所在。2. 动态规划思路分析2.1 单人问题的DP解法回顾对于单人取数问题我们可以定义dp[i][j]表示从(1,1)走到(i,j)时能获得的最大和。状态转移方程为 dp[i][j] max(dp[i-1][j], dp[i][j-1]) grid[i][j]这个方程表示当前格子的最大值来自上方或左方的较大值加上当前格子的数值。2.2 双人问题的扩展思路当问题扩展到两个人时我们需要考虑两人的路径可能会交叉的情况。这时候简单的二维DP就不够用了需要升维处理。我们可以定义dp[i1][j1][i2][j2]表示第一个人走到(i1,j1)第二个人走到(i2,j2)时的最大和。但这样会有O(N⁴)的空间复杂度对于N9的题目来说虽然可行但不够优雅。更聪明的做法是注意到两人的步数是同步的因为每次只能移动一步所以可以用步数k作为一维即dp[k][i1][i2]表示两人都走了k步第一个人在i1行第二个人在i2行时的最大和。因为ki1j1-1i2j2-1所以j1和j2可以通过k和i1、i2计算得出。3. 具体实现细节3.1 状态转移方程定义dp[k][i1][i2]为两人都走了k步第一个人在i1行第二个人在i2行时的最大和。那么状态转移需要考虑四种情况两人都从上方移动下来第一人从上方第二人从左方第一人从左方第二人从上方两人都从左方移动过来状态转移方程为 dp[k][i1][i2] max( dp[k-1][i1-1][i2-1], dp[k-1][i1-1][i2], dp[k-1][i1][i2-1], dp[k-1][i1][i2] ) (i1 i2 ? grid[i1][k1-i1] : grid[i1][k1-i1] grid[i2][k1-i2])3.2 边界条件处理初始状态dp[0][1][1] grid[1][1]两人都在起点当i1或i2超出网格范围时对应的状态无效当j1或j2超出网格范围时对应的状态也无效3.3 空间优化技巧由于dp[k]只依赖于dp[k-1]所以可以使用滚动数组技术将空间复杂度从O(N³)优化到O(N²)只需要保存当前步和前一步的状态即可。4. 代码实现示例#include iostream #include algorithm using namespace std; const int N 10; int grid[N][N]; int dp[2*N][N][N]; int main() { int n; cin n; int x, y, v; while (cin x y v, x || y || v) { grid[x][y] v; } for (int k 2; k 2*n; k) { for (int i1 1; i1 n; i1) { for (int i2 1; i2 n; i2) { int j1 k - i1, j2 k - i2; if (j1 1 || j1 n || j2 1 || j2 n) continue; int curr dp[k][i1][i2]; curr max(curr, dp[k-1][i1-1][i2-1]); curr max(curr, dp[k-1][i1-1][i2]); curr max(curr, dp[k-1][i1][i2-1]); curr max(curr, dp[k-1][i1][i2]); if (i1 i2) { curr grid[i1][j1]; } else { curr grid[i1][j1] grid[i2][j2]; } } } } cout dp[2*n][n][n] endl; return 0; }5. 算法优化与变种5.1 时间复杂度分析原始算法的时间复杂度是O(N³)因为有三层循环外层k循环2N次中层i1循环N次内层i2循环N次对于NOIP竞赛中的N9来说这个复杂度完全可接受。5.2 空间优化实现使用滚动数组优化空间int dp[2][N][N]; int now 0, prev 1; for (int k 2; k 2*n; k) { swap(now, prev); for (int i1 1; i1 n; i1) { for (int i2 1; i2 n; i2) { // 同上状态转移 } } }5.3 问题变种思考如果允许更多路径如三个人怎么办思路相同继续增加DP维度即可但复杂度会急剧上升如果网格很大如N100怎么办需要考虑更高效的算法或近似算法如果移动方向增加如允许斜向移动怎么办状态转移需要考虑更多情况6. 竞赛技巧与注意事项6.1 调试技巧对于小规模数据如N2或3可以手工计算验证程序正确性打印中间状态特别是边界情况注意数组下标是否越界6.2 常见错误忘记处理两人走到同一格时数字只能取一次的情况边界条件处理不当如k1时的特殊情况数组初始化不充分导致初始状态错误6.3 竞赛策略先解决单人问题确保基础DP正确再扩展到双人情况逐步增加复杂度对于部分分可以考虑较简单的解法如记忆化搜索7. 实际应用与扩展虽然这个问题看起来是纯理论性的但它实际上有许多实际应用场景资源分配问题如两个工人同时从不同路径收集资源网络流量优化两条数据路径的最优传输物流路径规划两辆运输车的最优配送路线这类问题的核心思想——多维动态规划在解决复杂优化问题时非常有用。掌握这个技巧可以帮助我们更好地处理现实世界中的各种路径优化和资源分配问题。

相关推荐

DNS负载均衡原理与实战优化指南
DNS负载均衡原理与实战优化指南

1. DNS负载均衡的本质与价值当我们在浏览器输入www.example.com时,背后发生的DNS解析过程远比表面看到的复杂。传统的单点解析就像把所有鸡蛋放在一个篮子里——一旦服务器宕机,整个服务就会瘫痪。而DNS负载均衡通过将访问流量分散到多个服务器节点&… · 2026/11/2 16:45:29

小程序收货地址标准化:地址解析API的工程边界与落地
小程序收货地址标准化:地址解析API的工程边界与落地

简介:面向微信小程序开发者的地址处理实践资源,聚焦快递收货地址的智能识别与标准化。借助腾讯云地址解析 API,把用户填写的非结构化地址文本拆解为省、市、区等地理要素,减少手动选择与录入误差,适用于电商、物流等需… · 2026/11/2 16:45:29

前端日期显示最佳实践:从语义化到国际化
前端日期显示最佳实践:从语义化到国际化

1. 项目背景与意义"一月十九日"这个看似简单的日期标记&#xff0c;实际上蕴含着丰富的文化内涵和技术实现可能性。作为Web开发领域的基础元素&#xff0c;日期时间的展示与处理一直是前端开发中的重要课题。HTML5标准中专门引入了<time>元素来处理日期时间数据… · 2026/11/2 16:45:29

Anaconda3 安装与首配实战:PATH、虚拟环境与依赖验证避坑指南
Anaconda3 安装与首配实战:PATH、虚拟环境与依赖验证避坑指南

简介&#xff1a;面向Python数据科学初学者、高校学生与自学者&#xff0c;这份Anaconda安装指南围绕三大主流操作系统&#xff0c;梳理从官网获取安装包到完成基础环境配置的关键环节。压缩包内仅含1个docx文件&#xff0c;大小约14KB&#xff0c;篇幅轻量&#xff0c;便于本地… · 2026/11/3 13:21:04

TensorFlow实战全记录:环境配置、图像分类与PyTorch选型对比
TensorFlow实战全记录:环境配置、图像分类与PyTorch选型对比

TensorFlow&#xff1a;从入坑到上手的完整记录&#xff0c;以及和PyTorch的账到底怎么算 做深度学习这几年&#xff0c;TensorFlow一直是我绕不过去的一环。从最早接触TF 1.x那种写个计算图还要开session的别扭日子&#xff0c;到现在Keras一把梭的顺手程度&#xff0c;说真的… · 2026/11/3 13:21:04

PHP+WebSocket双模式实时聊天室架构设计与实现
PHP+WebSocket双模式实时聊天室架构设计与实现

1. 项目概述&#xff1a;双模式架构的PHPWebSocket实时聊天室 这个项目实现了一个基于PHP和WebSocket技术的高性能实时聊天室系统&#xff0c;其核心创新点在于采用了"双模式架构"设计。所谓双模式&#xff0c;指的是系统同时支持传统的HTTP轮询和现代的WebSocket协议… · 2026/11/3 13:21:04

Elementor模板套件Baha:高转化率着陆页设计指南
Elementor模板套件Baha:高转化率着陆页设计指南

1. Baha模板套件概述&#xff1a;Elementor生态中的专业着陆页解决方案Baha是一款专为Elementor页面构建器设计的免费应用类产品着陆页模板套件&#xff08;Template Kit&#xff09;&#xff0c;主要面向移动应用开发者、SaaS服务商和数字产品创作者。这个模板套件包含了完整的… · 2026/11/3 13:21:04

安卓开发实战:独居老人安全监测工具技术解析
安卓开发实战:独居老人安全监测工具技术解析

1. 项目概述&#xff1a;独居老人安全监测工具的技术实现 "死了么APP"这个看似戏谑的名称背后&#xff0c;实际上是一个严肃的社会需求解决方案。作为一款专为独居老人设计的安全监测工具&#xff0c;Keep Alive Lite安卓版通过轻量级的技术手段实现了对用户生命状态… · 2026/11/3 13:21:04

雷达基数据二进制解析:字节序、信息头与定点编码避坑
雷达基数据二进制解析:字节序、信息头与定点编码避坑

简介&#xff1a;《雷达基数据格式说明》面向气象数据处理、雷达产品开发及遥感教学场景&#xff0c;系统梳理CINRAD SA/SB与CA/CB雷达基数据的字节级组织规则&#xff0c;帮助读者建立二进制文件的读取依据。文档围绕雷达信息头、径向数据收集时间、儒略日、不模糊距离、方位角… · 2026/11/3 13:20:03

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/2 13:10:28

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/3 6:04:24

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/3 5:52:46

STM32F411RE与MAX14431实现SPI隔离:工业现场抗共模干扰实战
STM32F411RE与MAX14431实现SPI隔离:工业现场抗共模干扰实战

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/3 1:01:59

ESP32+大模型AI硬件开发:从Demo到产品的8个工程问题
ESP32+大模型AI硬件开发:从Demo到产品的8个工程问题

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/3 1:01:59

基于MAX14431BAEE+与PIC18F85J10的SPI隔离方案设计与实践
基于MAX14431BAEE+与PIC18F85J10的SPI隔离方案设计与实践

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/3 1:01:59

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/2 13:10:28

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/3 6:04:24

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/3 5:52:46

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码