动态规划入门：先把“状态”想清楚

很多人 DP 写不出来，是因为没定义清楚状态。

套路：1) dp[i] 表示什么；2) 转移方程；3) 边界；4) 遍历顺序。
比如爬楼梯：dp[i] = 到第 i 阶的方法数，dp[i]=dp[i-1]+dp[i-2]。
先把这四个问题写在纸上，代码自然就出来了。