进阶算法-动态规划

动态规划算法 实现基本步骤4步（以不同路径题目为例）：

• 确定状态表示：令 dp[i][j] 是到达 i, j 最多路径；
• 划分最优子结构：路径总和 dp[i][j] 可以拆分为 dp[i-1][j] 与 dp[i][j-1] 子路径；
• 得出状态转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]；
• 确定边界（base case，最简单情况）：对于第一行 dp[0][j]，或者第一列 dp[i][0]，由于都是在边界，所以只能为 1。

1、不同路径

• 不同路径
• 不同路径 II

2、最短路径

• K 站中转内最便宜的航班