坐标型动态规划

dp[i]表示从起点到坐标i的最优值/方案数/可行性
dp[i][j]表示从起点到坐标i,j的最优值/方案书/可行性
代表题：Triangle、Unique Paths

前缀型之划分型

dp[i]表示之前i个字符的最优值/方案数/可行性
dp[i][j]表示前i个字符分为j个部分的最值/方案数/可行性
代表题：Word Break, Word Break III

前缀型之匹配型

dp[i][j]表示第一个字符串的前i个字符匹配上第二个字符串的前j个字符的最优值/方案数/可行性
代表题：Longest Common Subsequence, Wildcard Matching

区间型

dp[i][j]表示i~j的最优值/方案数/可行性
代表题：Stone Game, Burst Ballons

背包型

dp[i][j]表示前i个物品里选出一些物品组成和为j的大小的最优值/方案数/可行性
代表题：Backpack系列

01背包——第一种状态表示

状态state
dp[i][j]表示前i个数里挑若干个数是否能组成和为j
方程function
dp[i][j] = dp[i - 1][j] or dp[i - 1][j - A[i]] 如果j >= A[i]
dp[i][j] = dp[i - 1] 如果 j < A[i]
初始化initialize
dp = [0][0] = true
dp[0][1…m] = false
答案answer
使得dp[n][v], 0 <= v <= m 为true的最大v

三种不适用DP的场景

求所有的具体方案
只求出一个具体方案还是可以用DP来做的

输入数据的无序的
背包类动态规划不适用此判断条件，除去背包问题后方向：逐行生成数据

暴力算法的复杂度已经是多项式级别
动态规划擅长与优化指数级别复杂度到多项式级别复杂度
不擅长优化n^3到n^2