动态规划的题目一直挺头疼的，多次CCF-CSP和机试都卡住了，痛定思痛，好好学，好好刷
动态规划最核心的就是找出状态转移方程，找到边界条件，这个找出来了基本上就解决问题了
斐波那契数列类
这一类题目都是维护一个数组就可以了
爬楼梯
一次可以爬1/2节楼梯，爬到第n层有多少中方法
设$dp[i]$为爬到第$i$层的方法数
边界条件
$$
dp[0]=0,dp[1]=1
$$
状态转移方程
$$
dp[i]=dp[i-1]+dp[i-2],i \ge 2
$$
这种首先维护出数组然后查表的速度最快
斐波那契
$dp[0]=0,dp[1]=1,dp[i]=dp[i-1]+dp[i-2],i \ge 2$
最小花费爬楼梯
有一个cost数组，问爬到顶最小花费是多少，规模是$n$，标号是$0 \to n-1$
设$dp[i]$为爬到第$i$层顶的最小花费，实际是到$n$
边界条件是
$$
dp[0]=0,dp[1]=0
$$
状态转移方程是
$$
dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
$$
打家劫舍
打家劫舍可以抽象成数组最大不相邻和
有一个数组nums，求最大不相邻和
一开始想到的状态转移方程挺奇葩的
解法1
设$dp[i]$为包含第$i$个数的最大不相邻和
$$
dp[i]=\max_{j=1}^{i-2}(dp[j])+nums[i]
$$
求完之后再遍历一遍dp，找到最大的
这样子时间复杂度是$O(n^2)$但是速度比解法2还快(?)
破案了，官方判题的执行用时与多个因素有关，存在不稳定性
解法2
时间复杂度为$O(n)$
$dp[i]$表示前$i$个数的最大不相邻和
边界条件
$$
dp[0]=nums[0],dp[1]=max(nums[0],nums[1]),
$$
状态转移方程
$$
dp[i]=max(dp[i-1],dp[i-2]+nums[i]),i \ge 2
$$
删除并获得点数
建立一个数组样式的哈希表，然后就是求数组最大不相邻和
