商业网站建设实训指导书,php mysql开发的网站开发,牟平网站制作,做微商有卖鞋子的网站吗本文主要内容为基础DP#xff0c;内容来源为《算法导论》#xff0c;总结不易#xff0c;转载请注明出处。 后续会更新出kuanbin关于基础DP的题目...... 动态规划#xff1a; 动态规划用于子问题重叠的情况#xff0c;即不同的子问题具有相同的公共子子问题#xff0c;在… 本文主要内容为基础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)。 1 #include iostream2 #include cstring3 #include algorithm4 using namespace std;5 6 const int maxn 1000, INF -0x3f3f3f3f;7 long long dp[maxn], s[maxn];8 long long p[maxn] {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};9 long long q;
10
11 long long memoized_cut_rod(int n) {
12 if(dp[n] 0) return dp[n];
13 if(n 0) q 0;
14 else q INF;
15 for(int i 1; i n; i )
16 q max(q, p[i] memoized_cut_rod(n - i));
17 dp[n] q;
18 return q;
19 }
20
21 long long bottom_up_cut_rod(int n) {
22 dp[0] 0;
23 for(int j 1; j n; j ) {
24 q INF;
25 for(int i 1; i j; i ) {
26 q max(q, p[i] dp[j - i]);
27 }
28 dp[j] q;
29 }
30 return dp[n];
31 }
32
33 int main () {
34 long long n;
35 memset(dp, -1, sizeof dp);
36 while(cin n) {
37 long long ans memoized_cut_rod(n);
38 printf(%d\n, ans);
39 ans bottom_up_cut_rod(n);
40 printf(%d\n, ans);
41 }
42 } 重构解 long long bottom_up_cut_rod(int n) {dp[0] 0;for(int j 1; j n; j ) {q INF;for(int i 1; 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 1000, INF 0x3f3f3f3f;
long long dp[maxn];long long calculate_fib(int n) {if(n 0 n 1) return 1;for(int i 2; i n; i )if(dp[i] 0) dp[i] dp[i - 1] dp[i - 2];return dp[n];
}int main () {long long n;for(int i 0; i maxn; i ) dp[i] -INF;dp[0] dp[1] 1;while(cin n) {cout calculate_fib(n);}
} 转载于:https://www.cnblogs.com/bianjunting/p/10551303.html
