动态规划：最小路径和问题解析

动态规划：最小路径和问题解析

1. 最小路径和

1.1 题目来源

本题来自力扣第 64 题。

1.2 题目解读

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。这类似于经典的珠宝问题，区别在于求解最小路径和。

1.3 思路讲解

对于动态规划题目，首先创建 dp 表。根据题目要求，需要用到一个二维 dp 表。

1. 状态表示

对于线性的 dp 表，通常结合经验与题目要求进行状态表示。dp[i][j] 可以表示为到达 [i, j] 位置时的最小路径和。

2. 状态转换方程

到达 [i, j] 位置的方式无非两种：从上面到达，或者从左边到达。计算两者之间的最小值，再加上当前位置本身的值，即可推测出状态转换方程。