今天做了leetcode上动态规划的部分题目，从“斐波那契类型”做起的，文章记录自己解题时的一些想法。
70. 爬楼梯
需要n阶能爬到顶楼，每次只能爬1或2阶，要求的是爬到顶楼有多少种方法。
首先n=1时显然最多有一种方法，n=2时显然最多有两种方法；当n等于3时，这里有两种方法，从1爬2阶或n从2爬1阶，后续所有n，无外乎这两种爬法，这两种爬法各自对应的所有爬法之和，即为所求；记f(n)为n阶时最多的爬楼方法，则f(n)=f(n-1) + f(n-2)，如此便成了一个斐波那契数列的问题。
此种问题一个求法是使用“滚动数组”思想，因为f(n)只与它前两个递推项有关，想象有三个盒子，p、q、r，分别对应f(n-2)、f(n-1)、f(n)，迭代一次就左移一次，p=q，q=r，r由该p、q运算产生。这第一个题卡了很久，看了题解学会了这个思想，后面多次用到。
509. 斐波那契数
求斐波那契数列，斐波那契数问题算是爬楼梯问题蕴含的数学问题，爬楼梯问题是斐波那契数问题的应用。同样使用“滚动数组”来解。
1137. 第N个泰波那契数
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
斐波那契数的变体，第四个数由前面三个数产生，加一个滚动数组来解决。
746. 使用最小花费爬楼梯
最小花费爬楼梯的问题给定一个花费数组cost，其中cost[i]代表踏上i阶梯需要支付的费用，从i阶梯向上可以选择爬一阶或者两阶。
这道题与爬楼梯问题类似，都是每次只能上1阶或者2阶，区别在于这里每一步都是有代价的，不同于爬楼梯问题要找尽可能多的爬法，因此将从-1和从-2阶的最大爬法相加，这里比较从-1和从-2阶到达的花费，并取其中较小者作为花费。递归当然是可解的，但是动态规划本就是为了简化递归，因为该类问题当画出递归树就能发现其中存在大量的重复计算，动态规划将计算中的步骤结给保存下来，简化后续计算。
初始化数组dp，其中dp[i]代表到达阶梯i时的累计最小花费。于是便有两种情况，即踩i和不踩idp[i] = min(dp[i-2] + cost[i-2], dp[i-1] + cost[i-1])，可以从下标 i-1 使用 cost[i−1]的花费达到下标 i，或者从下标 i−2 使用 cost[i−2]的花费达到下标 i，i从2开始，dp数组的两端，一端是dp[n]即为成功到达顶部（已脱离阶梯，因为len(cost)==n）的最小花费；另一端是dp[0]，dp[1]的初始值，从初始状态可以直接选择0或1开始的，因此dp[0]==dp[1]==0。
误区：这儿一直有一个想法是把状态转移方程列为dp[i] = min(dp[i-2]+cost[i], dp[i-1])，即试图将dp数组认为是“踩i后的最小花费”，但是决定踩或不踩i是未知的，我们只能用“到达”来表示，即踩i前的最小花费。
198. 打家劫舍
打家劫舍很经典，问题是这样的：沿街有一排房屋，每个房屋都有若干现金，小偷计划去偷取，即谋求窃取金额最大化，但是有个规定是不能连续偷两家。给定输入数组nums，nums[i]代表房屋i中的现金。
打家劫舍就适合用上面“误区”中的思想，分为偷i和不偷i能获得的最大金额，如果不偷i，则能获得的金额为：dp[i-1]，如果偷i，则获得的金额为：dp[i-2]+nums[i]；（这里可能会有疑问说，偷i也没说就要偷dp[i-2]为什么要用dp[i-2]+nums[i]，是的，但是dp[i-2]包含的意思时前n-2间房屋能获得的最大金额，也是两种情况，即偷i-2和不偷i-2，以此递推）将dp描述为前i间房屋能偷到的最高金额数，则有状态转移方程：dp[i] = max(dp[i-2] + nums[i], dp[i-1])。那么dp[0]和dp[1]分别是什么呢？显然如果说“前1间房屋能偷盗的最大金额”，即只有一间房屋时，dp[0]就为nums[0]，dp[1]为max(dp[0], dp[1])。
740. 删除并获得点数
这个问题有点拗口，给定一个证书数组nums，可以任选一个nums[i]，删除并获得所有点数，之后就要删除所有nums[i]-1和nums[i]+1的值，求可以获得的最大点数。
点数是允许有重复的，例如有3个3，那么如果选择了3，就等于选择了+9点数（3*3），与此同时3-1=2和3+1=4（如果有）的所有点数都将被删除；也就是说，不能选相邻的，是不是就跟打家劫舍一个思路了？打家劫舍中，不能偷相邻的房屋，跟偷了房屋3后房屋2和房屋4中金额清零是一个道理。
于是乎，首先要构造房屋，找到给定nums中的最大值max，由最大值max构造长度为max+1的“房屋”，即数组nums，“房屋”中的金额，即为对应的数字乘以重复次数。再用打家劫舍的思路解决，即可。