[leetcode][DP] DP Notes

当所面对的优化问题能够被划分为若干个相互关联的子问题，并且这些子问题的解在后续计算中会被反复调用时，可考虑采用动态规划方法进行求解。

运用动态规划需满足以下两个基本条件：

1. 优化子结构特性：整体问题的最优解由各个子问题的最优解构成，通过依次求解这些子问题，可以实现从高层到基层的整体求解过程。
2. 子问题重叠性：在解决整个问题的过程中，多个子问题的解会被多次调用。为提高效率，通常会将这些子问题的最优解存储起来，从而逐步构建出最终的最优解。

在处理动态规划类问题时，最关键的一环在于确立递归关系式。

64.最小路径和问题解析

假设存在一个由非负整数构成的 m x n 网格，要求确定从左上角出发至右下角的一条路径，使得该路径所经过的所有数字之和达到最小值。

说明：在移动过程中，每一步仅允许选择向下或向右的方向进行移动。

输入示例：
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出结果：7
解释：由于路径 1→3→1→1→1 的总和为所有可能路径中最小的，因此该路径被选为最优解。

设定一个二维数组 dp，其中 dp[i][j] 表示从坐标 (i,j) 出发到达网格右下角的最小路径和。

计算公式为：dp[i][j] = Math.min(dp[i][j+1], dp[i+1][j]) + grid[i][j];