本文主要内容为基础DP，内容来源为《算法导论》，总结不易，转载请注明出处。
后续会更新出kuanbin关于基础DP的题目......
动态规划：
动态规划用于子问题重叠的情况，即不同的子问题具有相同的公共子子问题，在这种情况下分治算法会做许多不必要的工作，它会反复求解那些子子问题使得程序边的缓慢。而动态规划则对每个问题 只求解一次，将其解保存在一个表格中，从而避免一些不必要的重复计算。
动态规划常用来求解最优化问题，这类问题可以有很多解，每个解都有一个值，我们希望寻找具有最优值的解，我们称这样的解为问题的一个最优解，而不是最优解，因为可能有多个最优解。
动态规划设计算法的一般步骤：
1.刻画一个最优解的结构特征。
2.递归的定义最优解的值。
3.计算最优解的值，通常采用自地向上的方法。
4.利用计算出的信息构造一个最优解。
动态规划的两种基本解题步骤：
第一种为自顶向下法：此方法仍按自然的递归形式编写过程，但过程中会保存每个子问题的解。当需要一个子问题的解时，过程中会首先检查是否此问题已经被求解，如果是则直接返回该解，否则按通常的方式计算，我们称这个递归过程时带备忘的，因为他记住了之前的计算结果，不会进行重复的计算。
第二种为自底向上法：这种方法一般需要恰当定义子问题的规模的概念，使得任何子问题都只依赖更小的子问题求解。因而我们可以将子问题的规模排序按由小到大的顺序进行求解。当求解某个子问题时，它所依赖的更小的子问题已经得到解决，结果已经保存。每个子问题也只需求解一次。
最优子结构：
问题的最优解由相关子问题的最优解构成，这些子问题可以独立求解。
重构解：
在求解过程中保存相应的状态到另一个辅助数组中即可。
例：钢条切割问题：一根长度为n的钢条，切割不同的长度 i 对应不同的价格p[ i ], 问你如何切割一根钢条使得利益最大化。
n = i1 + i2 + ... + ik;
递推式：
rn = max(pn, r1 + r(n-1), r2 + r(n-2)...r(n-1) +r1)。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std; const int maxn = , INF = -0x3f3f3f3f;
long long dp[maxn], s[maxn];
long long p[maxn] = {, , , , , , , , , , };
long long q; long long memoized_cut_rod(int n) {
if(dp[n] >= ) return dp[n];
if(n == ) q = ;
else q = INF;
for(int i = ; i <= n; i ++)
q = max(q, p[i] + memoized_cut_rod(n - i));
dp[n] = q;
return q;
} long long bottom_up_cut_rod(int n) {
dp[] = ;
for(int j = ; j <= n; j ++) {
q = INF;
for(int i = ; i <= j; i ++) {
q = max(q, p[i] + dp[j - i]);
}
dp[j] = q;
}
return dp[n];
} int main () {
long long n;
memset(dp, -, sizeof dp);
while(cin >> n) {
long long ans = memoized_cut_rod(n);
printf("%d\n", ans);
ans = bottom_up_cut_rod(n);
printf("%d\n", ans);
}
}
重构解：
long long bottom_up_cut_rod(int n) {
dp[] = ;
for(int j = ; j <= n; j ++) {
q = INF;
for(int i = ; i <= j; i ++) {
if(p[i] + dp[j - i] > q) {
q = max(q, p[i] + dp[j - i]);
s[j] = i;
}
}
dp[j] = q;
}
return dp[n];
}
while(n) {
cout << s[n] << '\t';
n = n - s[n];
}
例二：求斐波纳挈数
#include <iostream>
using namespace std; const int maxn = , INF = 0x3f3f3f3f;
long long dp[maxn]; long long calculate_fib(int n) {
if(n == && n == ) return ;
for(int i = ; i <= n; i ++)
if(dp[i] < ) dp[i] = dp[i - ] + dp[i - ];
return dp[n];
} int main () {
long long n;
for(int i = ; i < maxn; i ++) dp[i] = -INF;
dp[] = dp[] = ;
while(cin >> n) {
cout << calculate_fib(n);
}
}
