动态规划解决网格最小路径和问题

1. 题目分析与解题思路

1.1 题目理解与建模

P6649 「SWTR-5」Grid题目描述了一个n×m的网格，每个格子包含一个整数值。玩家从第n行的任意位置出发，按照特定规则移动，目标是找到一条路径使得经过的格子数值之和最小（重复经过的格子只计算一次）。

关键规则解析：

1. 移动规则：
   • 第一次进入某行i的位置为(i, r_i)
   • 在(i, r_i)时只能向左或向上移动
   • 在其他位置可以向左、向右或向上移动
2. 得分计算：所有经过格子的数值之和（重复经过只算一次）

这个问题可以建模为动态规划问题，因为：

• 具有最优子结构：当前行的最优解依赖于上一行的解
• 具有重叠子问题：不同路径可能会经过相同的子问题

1.2 算法选择与复杂度分析

选择动态规划算法的原因：

1. 网格问题天然适合DP解法
2. 移动规则限制了状态转移的方向
3. 需要记录每行的首次进入位置

时间复杂度分析：

• 预处理：O(nm)（翻转网格）
• DP计算：每行需要两次遍历（从左到右和从右到左），总体O(nm)
• 总复杂度：O(nm)，对于n,m≤1000是可行的

空间复杂度：

• 需要存储原始网格和DP表：O(nm)
• 可以使用滚动数组优化到O(m)

2. 动态规划实现详解

2.1 状态定义与初始化

状态定义：

• f[i][j]：到达第i行第j列时的最小得分
• val[i][j]：网格中第i行第j列的值（注意题目中的行号是反的）

初始化技巧：

• 将网格上下翻转，方便从第1行开始处理
• 初始值设为极大值（0x7f7f7f7f）
• 边界条件：第0行的f值为0（因为从第1行开始计算）

cpp复制const ll maxn=1e3+84;
ll n,m,ans=0x7f7f7f7f,val[maxn][maxn],f[maxn][maxn],hzn[maxn],qzn[maxn];

2.2 状态转移方程

核心状态转移分为三个步骤：

1. 从左到右计算qzn数组：

   cpp复制for(ll j=1;j<=m;j++)
       qzn[j]=min(qzn[j-1],0ll)+val[i][j];
   

   • qzn[j]表示从该行最左端到j