动态规划

经典动态规划问题

问题	状态定义	状态转移方程	初始化
斐波那契数列	dp[i] 表示 F(i)	dp[i] = dp[i-1] + dp[i-2]	dp[0] = 0, dp[1] = 1
爬楼梯	dp[i] 表示到第 i 阶的方法数	dp[i] = dp[i-1] + dp[i-2]	dp[0] = 1, dp[1] = 1
解码方式	dp[i] 表示前 i 个字符的解码方式数	dp[i] = dp[i-1] (if s[i] valid) + dp[i-2] (if s[i-1..i] valid)	dp[0] = 1
最长递增子序列（LIS）	dp[i] 表示以 nums[i] 结尾的 LIS 长度	dp[i] = max(dp[j] + 1) for j < i if nums[j] < nums[i]	dp[i] = 1（初始每个元素单独成序列）
0-1 背包问题	dp[i][j] 表示前 i 个物品在容量 j 时的最大价值	dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])