坐标型

状态:
f[x] 从起点到坐标x的状态,
f[x][y]: 从起点到坐标`[x][y]的状态
方程: 研究走到x, y 这个点之前的一步
初始化: 起点
答案: 终点

题目

64. Minimum Path Sum

function : f[x][y] = min(f[x-1][y], f[x][y-1]) + grid[x][y]

62. Unique Paths

63. Unique Paths II

function: f[x][y] = f[x-1][y] + f[x][y-1]

70. Climbing Stairs

function: f[i] = f[i-1] + f[i-2]

55. Jump Game

state: f[i]: 能否到第 i 个位置
function: f[i] = OR(f[j], j < i && j can reach i)

45. Jump Game II

state: f[i]: 跳到第 i 个位置最少要几步
function: f[i] = min {f[j] + 1, j < i && j can reach i}

300. Longest Increasing Subsequence

state: f[i]: 到 i 为止的最大上升序列
function: f[i] = max{f[j]+1} for j < i && nums[j] <= nums[i]

221. Maximal Square

state: f[i][j]: 表示以 i, j 作为正方形右下角的最大边长值
function: f[i][j] = min(f[i-1][j], f[i][j-1], f[i-1][j-1]) + 1 for matrix[i][j] == 1
f[i][j] = 0 for matrix[i][j] == 0

174. Dungeon Game

这一题是比较特殊的题目, 需要进行逆向考虑. int need = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
dp[i][j] = need <= 0 ? 1 : need;

91. Decode Ways

s[i - 1] == '0': ways[i + 1] = ways[i - 1];
s[i-1] != '0' && stoi(s.substr(i-1, 2)) <= 26: ways[i+1] = ways[i] + ways[i-1]
ways[i + 1] = ways[i]: all others