第十六周是C++课程设计的实训周，我们的课程设计任务是在nyoj上任选三到难度为3级以上的题目，我之前是选了几道有关贪心算法的题目，后来发现做贪心的题可能有点简单了，所以我选择了之前一直想学习，但是没什么机会学习的动态规划，算是给课程设计一个面子（233），也是给自己施加点压力，所以这两天我会把我所学习到的动态规划知识整理到博客里面供日后复习，也方便大家一起交流。
目录：
1、问题与子问题
2、三大性质
3、状态与转移
4、记忆化搜索
问题与子问题：
我们先来看一个例子：
把一头大象装到冰箱里面需要几步：
1、打开冰箱门
2、把大象装进冰箱
3、关上冰箱门
我们认为这是一个时间复杂度为O(1)的算法
把两头大象装到冰箱里面需要几步：
1、打开冰箱门
2、把大象装进冰箱
3、关上冰箱门
4、换一个冰箱
5、打开冰箱门
6、把大象装进冰箱
7、关上冰箱门
我们认为这是一个规模为2的算法，它可以被分解为两个规模为1的算法
把N头大象装到冰箱需要几步：
1、当n = 1时，那么
· 打开冰箱门
· 把大象装进冰箱
· 关上冰箱门
2、当n>=1时，那么
· 解决“把n-1头大象装进冰箱的问题”
· 换一个冰箱
· 打开冰箱门
· 把大象装进冰箱
· 关上冰箱门
“把n-1头大象装进冰箱”即为“把n头大象装进冰箱”的子问题
刚才的方法略有些冗余，我们可以找到一个更好的边界化简之：
1、当n = 0时，啥也不用做
2、解决“把n−1头大象装进冰箱”的问题
换一台新的冰箱
打开冰箱⻔把最后1头大象装进去
关上冰箱门
在实际写程序的过程中，我们也可以通过寻找更好的边界条件来简化代码
说完这些、似乎已经搞懂了什么叫做问题、什么叫做子问题了，来看一个更好玩的例子：
假设把有两种冰箱，一种可以一次性装三头大象，成本为5元，还有一种是一次性可以装五头大象，成本为8元，我们需要把n头大象装进冰箱，求所需要费用最少为多少：
问题分析：
设“把n头大象装进冰箱的最小费用”为f(n)
这是一个规模为n的问题，我么可以将它转换成规模为n-3和n-5的问题
所以我们只需要分别考虑f(n-3)和f(n-5)，得到状态转移方程如下：
f(n) = min {f(n-3) + 5 , f(n-5) + 8}
得出转移方程后，我们可以尝试用最朴素的搜索算法来实现，自己写一下再往后看？
int solve (int n)
{
if(n <= 0) return 0;
return min(solve(n-3) + 5 , solve(n-5) + 8);
}
代码看上去很简洁，这很递归，但是分析一下我们可以知道这是一个指数级别的算法，也就是说，如果问题规模很大，那么就有可能出现递归爆栈（Stack Overflow）
动态规划的核心思想就是通过记录重复的状态来进行优化：我们发现，在进行递归时，许多子问题被重复计算了很多次，做了大量的无用功。那么只要将他们记录下来，就可以节省下这些时间，可以将时间复杂度优化至线性，具体的做法有记忆化搜索和数组递推等，阅读下面的代码，不懂的在评论区留言。
const int N = 100005
int f[N];
bool vis[N]; //在外部初始化的bool数组里面都是false
int solve (int n)
{
if(n <= 0) return 0; //如果越界，返回0
if(vis[n] == true) return f[n]; //如果之前计算过，就不再重复计算
f[n] = min(solve(f[n-3] + 5 ), solve(f[n-5] + 8)); //如果没有，计算
vis[n] = true; //并将标记数组设标记，表示计算过
return f[n];
}
代码简化：我们刚刚使用了两个数组，在空间上有点浪费，我们可以只使用一个数组来进行标记，具体操作看代码：
const int N = 10005
int f[N];
void init () // 先将数组都初始化一个很奇怪的数
{
for(int i = 0 ; i < N ; ++i)
f[i] = -1;
}
int solve (int n)
{
if(n <= 0) return 0;
if(f[i] != -1) return f[i]; //如果不是奇怪的数，说明计算过，避免重复计算，return回去
f[n] = min(solve(n-3) + 5 , solve(n-5) + 8);
return f[n];
}
三大性质（有些我也不懂，直接从WIKI上粘上来的，QAQ）
1、重叠子问题：
动态规划的优化原理就是减少重复计算，而这一点正是依赖于重叠子问题这一性质。就如刚才所说的，每一个“相同”的子问题被计算了多次，因此可以被优化，如果子问题设计的过于精细，它们个不相同，就没有dp的用武之地了。
2、子问题最优性
刚才问题有一个性质：如果我们把一个问题分割成子问题，并计算它们的最优解，那么每个子问题的“子解”必然是这个子问题的最优解。简单来说，“如果想让整体最优，就要让每个部分都最优。”
然而，有一些问题不满足这个性质，就无法直接套用dp来解决。例如刚才的问题中，冰箱供应商搞活动，小冰箱满6台立减10元，那么我们从f(15)转移到f(18)时，f(15)的最优解（用3台大冰箱）并不是作为f(18)的子问题时的最优解（用6台小冰箱）的子解。
3、无后效性
子问题一旦确定，就不再改变，不受在这之后，包含它的更大的问题的求解决策影响。简单来说，“我们只考虑每个子问题的答案，而不需要考虑它具体是怎么得到的”。
举一个不满足性质的例子：如果大象被装进冰箱会不高兴，于是我们要将使用的大冰箱数量控制在某个范围内，那么显然子问题的具体解（用了几台大冰箱）就会对后续的解答产生影响，有后效性。
状态与转移
状态的设计：
简单来说，状态就是问题，状态并不是自然而然出现的，需要我们自己来抽象提炼。例如在刚才的大象装箱2问题中，状态n表示已经装了n头大象，维数是在一维，总共是n个，在一些更复杂的问题中，状态的维数可能更高，个数也可能更多。一般来说，状态可以通过若干个整数的"坐标"来表示，里例如在打折活动的大象装箱问题中，我们要同时记录已经装了几头大象，以及几台冰箱。
转移的设计：
设计完状态之后，我们需要考虑它们之间的转移，需要兼顾正确性和效率。如果是最优化问题，要注意子问题最优性是否被满足；如果是计数问题，则需要检查是否做到不重不漏。
今天是学习动态规划的第一天，主要是学习了很多概念方面的东西，再要抓紧学习一些应用方面的知识，比如背包问题之类的。
看完这一节，大家可以尝试写一写下面这道题，这是我课程设计的第一道题，可以说没有难度，有不懂的可以在评论区留言，谢谢。http://acm.hdu.edu.cn/showproblem.php?pid=2041
Comments | NOTHING