前缀型
划分型
使用一维数组dp[i]: 记录在下标为i的元素前砍一刀所得到的方案数/可行性
- decode ways 在i砍一刀，求组合，累加全部方案总数
- word break 在i砍一刀，看看能不能划分成单词
匹配型
使用二维数组dp[i][j]记录两个string之间的关系：
例1. dp[i][j] = s[0:i] 能够和 p[0:j]匹配的最长string
例2. dp[i][j] = s[0:i]通过多少次能够变成p[0:j]
- wildcard matching
- edit distance
区间型
有substring, subarray等字眼
使用二维数组dp[i][j]记录两个区间所代表的最优值/可行性/方案总数
接龙型
- 使用一维数组dp[i]: 以下标为i的元素结尾的最长长度
