基础DP(初级版)

  本文主要内容为基础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);
}
}
上一篇:Qt4中学习使用QtCharts绘图四:绘制柱状图


下一篇:hdu 5586 Sum 基础dp