DP 动态规划 #4
Description
DP 动态规划
Status: In progress
动态规划
动态规划 → 记忆化递归 有什么区别与联系？
-
dynamic programming （动态规划）是一类常用来解决优化问题的算法。它的最大特点是使用子问题的信息帮助解决父问题，使解题的难度减小。比如，求第1,000,002个斐波那契数这个问题看起来很复杂，但如果已知了第1,000,000和第1,000,001斐波那契数，事情就简单多了。
-
动态规划问题有一个显著的特点，就是子问题之间存在相互重叠。动态规划通过记录子问题的结果，保证每个子问题只计算一次，减少了时间浪费。动态规划的时间复杂度通常是多项式复杂度（即O(n)，k为非负常数），而不记录结果的算法由于重复计算，复杂度通常远高于动态规划，达到指数复杂度。
-
dynamic programming这个英文名词有些让人难懂。实际上，这里的programming不是指编程，而是数学上的一种解决优化问题的方法，叫做列表法(tabular method)，大致过程是将函数的不同变量值在表中列出并对表进行各种操作来求得结果。如果列表法是静态（static）的，则动态规划算法中，表格是慢慢增长的，先解决相对简单的子问题，然后通过子问题的结合求取父问题，这样表格好像是“动态”的。这就是dynamic programming的意思
- top-down通常以递归形式出现，从父问题开始，递归地求解子问题。top-down的求解过程通常与memoization结合，即将计算过的结果缓存在数组或者哈希表等结构中。当进入递归求解问题时，先查看缓存中是否已有结果，如果有则直接返回缓存的结果。
- bottom-up通常以循环形式出现。bottom-up的求解过程通常与tabulation结合，即先解最小的子问题，解决后将结果记录在表格中（通常是一维或二维数组），解决父问题时直接查表拿到子问题的结果，然后将父问题的结果也填在表中，直到把表格填满，最后填入的就是起始问题的结果。
动态规划 vs 分治
分治不需要考虑子问题的重复出现，动态规划需要。除此以外，两者都是根据子问题递归，并组合求解的。
动态规划 vs 贪心
- 贪心：每一步的最优解一定包含上一步的最优解，上一步之前的最优解无需记录
动态规划：全局最优解中一定包含某个局部最优解，但不一定包含上一步的局部最优解，因此需要记录之前的所有的局部最优解 - 贪心：如果把所有的子问题看成一棵树的话，贪心从根出发，每次向下遍历最优子树即可，这里的最优是贪心意义上的最优。此时不需要知道一个节点的所有子树情况，于是构不成一棵完整的树
动态规划：动态规划需要对每一个子树求最优解，直至下面的每一个叶子的值，最后得到一棵完整的树，在所有子树都得到最优解后，将他们组合成答案 - 贪心不能保证求得的最后解是最佳的，复杂度低
动态规划本质是穷举法，可以保证结果是最佳的，复杂度高
滚动数组
滚动数组是DP中的一种编程思想。简单的理解就是让数组滚动起来，每次都使用固定的几个存储空间，来达到压缩，节省存储空间的作用。起到优化空间，主要应用在递推或动态规划中（如01背包问题）。因为DP题目是一个自底向上的扩展过程，我们常常需要用到的是连续的解，前面的解往往可以舍去。所以用滚动数组优化是很有效的。利用滚动数组的话在N很大的情况下可以达到压缩存储的作用。
#include<bits/stdc++.h>
int main()
{
int i;
long long d[80];
d[0]=1;
d[1]=1;
for(i=2;i<80;i++)
{
d[i]=d[i-1]+d[i-2];
}
printf("%lld\n",d[79]);
return 0;
}
//滚动数组后不用申请那么大的数组
#include<bits/stdc++.h>
int main()
{
int i;
long long d[3];
d[1]=1;
d[2]=1;
for(i=2;i<80;i++)
{
d[0]=d[1];
d[1]=d[2];
d[2]=d[0]+d[1];
}
printf("%lld\n",d[2]);
return 0;
}