单序列
- state: f[i]表示前i个位置/数字/字符,第i个... • function: f[i] = f[j] ... j是i之前的一个位置• initialize: f[0]..
- answer: f[n]..
- 一般answer是f(n)而不是f(n-1)
- 因为对于n个字符,包含前0个字符(空串),前1个字符......前n个字符。
如果不是跟坐标相关的动态规划，一般有N个数/字符,就开N+1个位置的数组，第0个位置单独留出来做初始化
Word Break
- dfs
- dp
Unique Binary Search Tree
initialize: dp[0] = 1, dp[1] = 1
state: dp[i]: the number of unique BST, where the number i is the root of BST
state transition: dp[i] = dp[right] + dp[left]
result: dp[n]