动态规划大题解来啦！！
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
前言：
动态规划（dynamic programing（简称DP））通过记忆化的方式弥补了暴力搜索（如BFS，DFS等）重复计算某些区间的缺点。有的题目用动规甚至可以把时间复杂度从O(2^N) 降维打到O(N^2)。不过同时，这一算法也有一定门槛，是许多C++小白的一生之敌。
近期，我将会分两批，把ACGO官方的动规题单中的题目统一发放题解在一个帖子里面。这次的帖子是动规题单中相对简单的9道题（差不多占题单的50%）。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
动规步骤
在正式开始之前，我需要说明做动态规划题目的步骤以及必须确定的及部分：
第一步：
众所周知，动规算法的主心骨是DP数组。但是与递推算法不一样的是，不一定所有的DP数组都自带答案。而如果不知道DP数组的含义而盲目去做只会导致越做越废（比如说那时的我）。所以做动规题目的第一步是确定该怎样定义DP数组 （也就是确定“DP[i][j]” 或 “DP[i]”的含义）。
第二步：
这一步是难倒大部分人的部分，也就是推导动态转移方程。听起来很高深，说白了就是当你有了前几项的答案，如何得出下一步的答案。其实有两种办法。1.（这一种很有用）打表+总结+AC。2.当你牛到了一定程度可以直接推导计算+AC。
第三步：
有的人万事俱备了，但是之后一通乱写，结果全部爆红。原因就是没有初始化好。怎样初始化呢？你可以把自己的大脑想成一个计算机，先自己推一下，把那些无法用转移方程推出来的找出来，它们就是初始化的对象。
第四步：
遍历顺序。这一点也是不可忽略的。比如像01背包和完全背包，遍历顺序完全是相反的（这一点也是和递推很不一样的一点）。具体该怎样要随机应变（反正很重要）。
第五步：
万事俱备，顺水推舟就行。
以上几点可能大家暂时体验不到，现在步入正题。来人！把准备的九道题搬出来，让他们体验一一下具体的五步！！
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
九道题的题解
1.A7927.兔子数列
本题个人认为反而更像递推，就是一道毫无争议的模板题。DP[n]就是本题答案。而且动态转移方程也告诉我们了。唯一要注意的就是初始化。从道理上来讲，应该初始化DP[1]和DP[2]。
代码如下：
但是，有人过了离开了，有人还在研究。这题还可以只用三个变量解决。具体逻辑大家自己理。
代码：
2.A7928.钞票问题
本题也是动规模板题。相信很多新手都是在这里死磕贪心挂掉的（忽略玩特判的）。动规做法的DP定义也很简单，DP[n]就是答案。但是在动态转移方程上面，就和递推有所不同了。他并不是通过前面一两位来获得后面的答案。这里就要展现记忆化搜索的强大之处了。由于我们是从前往后推的，因此DP数组当前位置的前面的所有位数已经知道了。而只有三种情况达到这个答案：1.i - 1加了一个1元的钞票变成i。2.i - 5加了一个5元的钞票变成i。3.i - 11 加了一个11元的钞票变成i。因此，只需要在DP[i - 1],DP[i - 5]和DP[i - 11]中找到最小值并+1就可以了（记得判边界）。
代码如下：
3.A7929.不同的路径
这题不难，我们需要知道除了上边界以及左边界以外，对于每一个，要么从左边来，要么从上面来。所以DP[i][j] = DP[i - 1][j] + DP[i][j - 1]。对于上边界，只能从左边来；对于左边界，只能从上边来，所以全初始化为1。
代码如下：
4.A627.数字三角形
题单里面没有这题，是我自己补进来的。（当然是因为它很重要）。其实这和上一题是一个循序渐进的过程。上题是求方案数，这题是求最大值（想到Dj了么）。是上方和左上方两个方位，用max来取最值。
代码如下：
5.A7932.数塔升级版
这题和上一题大同小异，二叉改三叉了，最大改成了最小。但是我这题用另外一种方法来解——即用父节点先初始化子节点。看得懂的可以找机会帅一把。
代码如下：
6.A7933.数塔升级版2
这题看起来很难，有的人感觉像是广搜/深搜（结果看了看数据范围直接老实了）。但是我们要有逆向思维，还是从上往下推，具体思路和前两题差不多。只不过找答案的时候记得要在下面中间的格子找。
代码如下：
A7931.传球游戏
本体对于新手来说有难度，因为需要开新的一维用来从传一次球推导到传两次球……最后推导到传m次球。初始化DP[1][0]即可，因为一开始的球是在小蛮手里的。
代码如下：
8、9.A7934.最长上升子序列 A7956.导弹拦截
在题单里面有很多与这两题题相似的题，本帖就讲这两个两个，也算是为下篇开了个头。这两道题都是纯纯的模板题，与数塔相似,都使用贪心思想。在求答案方面有所不同，需要每一位都求一下。
代码如下：
导弹拦截：
最长上升子序列：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
如果本帖对你有用，请点一个赞，支持一下。
（AC君都点了，你不点一下？）
未完待续……
