特点:题目中直接包含坐标的概念
- State:
- f[x] 表示我从起点走到坐标x
- f[x][y] 表示我从起点走到坐标 x, y
- Function: 研究走到 x, y 这个点之前的一步
- Initialize : 起点
- Answer : 终点
技巧:
状态即是问题的答案
初始化一个二维的动态规划时,就去初始化第0行和第0列
例子:
一维坐标
爬楼梯 https://leetcode-cn.com/problems/climbing-stairs/
使用最小花费爬楼梯 https://leetcode-cn.com/problems/min-cost-climbing-stairs/
斐波那契数 https://leetcode-cn.com/problems/fibonacci-number/
第N个泰波那契数 https://leetcode-cn.com/problems/n-th-tribonacci-number/
跳跃游戏 https://leetcode-cn.com/problems/jump-game/ (动归会超时,贪心不超时,但动归思想和有意义)
最大子序和 https://leetcode-cn.com/problems/maximum-subarray/
二维坐标
不同路径 https://leetcode-cn.com/problems/unique-paths/
不同路径II (有障碍物)https://leetcode-cn.com/problems/unique-paths-ii/
最小路径和 https://leetcode-cn.com/problems/minimum-path-sum/
地下城游戏 https://leetcode-cn.com/problems/dungeon-game/ (从右下往左上递归)