单序列型
状态: f[i]: 表示前 i 个位置/数字/字符, 第 i 个
方程: f[i] = f[j]... j 是 i 之前的一个位置
初始化: f[0]
结果: f[n]
一般结果是f(n) 而不是 f(n-1) 因为对于 n 个字符, 包含前0个(空串), 前1个... 前 n 个.
题目
139. Word Break
state: f[i]: 前 i 个字符能否被完美切分
function: f[i] = OR{f[j] && j + 1 ~ i is a word} j < i
initialize: f[0] = true;
132. Palindrome Partitioning II
state: f[i] 前 i 个字符组成的子串能被分割为最少多少个
function: f[i] = min {f[j] + 1}, j < i && j + 1 - i is palindrome
initial: f[i] = i
answer: f[n] -1
198. House Robber
state: f[i] 表示前 i 个房子中, 偷到的最大值
function: f[i] = max(f[i-1], f[i-2] + A[i])
213. House Robber II
House Robber I 的升级版, 不同的地方就是要考虑第一步的区别, 解两次House Robber I 就可以了了.
338. Counting Bits
举例观察就会发现
dp[2^i + j] = dp[2^(i-1) + j] + 1