葛洲坝机电建设有限公司网站,餐馆餐饮装修设计,有声直播网站建设,安徽专业建网站2017.12.24 简单的动态规划 1.数字三角形(算法引入) 题目描述#xff1a;下图所示是一个数字三角形#xff0c;其中三角形中的数值为正整数#xff0c;现规定从最顶层往下走到最底层#xff0c;每一步可沿左斜线向下或右斜线向下走。设三角形有n层#xff0c;编程计算出从…2017.12.24 简单的动态规划 1.数字三角形(算法引入) 题目描述下图所示是一个数字三角形其中三角形中的数值为正整数现规定从最顶层往下走到最底层每一步可沿左斜线向下或右斜线向下走。设三角形有n层编程计算出从顶层到底层的一条路径使得该路径上的和最大输出最大值。(n100) 思路代码(搜索回溯) 最显而易见的思路既然要求一条最短的路径最简单的方法就是遍历所有的路径找到一条最优的。时间复杂度是O(2n)以下是搜索代码。 1 #include stdio.h2 #include math.h3 #include string.h4 int map[101][101],n;5 int count0,ans-20180101;6 void search(int x,int y){7 countmap[x][y];8 if(xn){9 if(countans)anscount;
10 }
11 else{
12 search(x1,y1);
13 search(x1,y);
14 }
15 count-map[x][y];
16 }
17 int main(){
18 scanf(%d,n);
19 int i,j;
20 for(i1;in;i){
21 for(j1;ji;j){
22 scanf(%d,map[i][j]);
23 }
24 }
25 search(1,1);
26 printf(%d\n,ans);
27 return 0;
28 } View Code 思路代码(分治法) 对于任意一个点我们可以把它的最大值和看成Max(sum[i1][j],[i1][j1])分解为两个规模更小的子问题。但是本质上和搜索没有区别所以时间复杂度还是O(2n)。 1 #include stdio.h2 #include math.h3 #include string.h4 int n,map[101][101];5 int fenzhi(int x,int y){6 if(xn)return map[x][y];7 int zi1,zi2,_max;8 zi1fenzhi(x1,y);9 zi2fenzhi(x1,y1);
10 if(zi1zi2)_maxzi2;
11 else _maxzi1;
12 return _maxmap[x][y];
13 }
14 int main(){
15 scanf(%d,n);
16 int i,j;
17 for(i1;in;i){
18 for(j1;ji;j){
19 scanf(%d,map[i][j]);
20 }
21 }
22 printf(%d,fenzhi(1,1));
23 return 0;
24 } View Code 思路代码(记忆化) 比搜索要更优。我们注意到不管是搜索还是分治它们都是O(2n)的时间复杂度是因为它们算了一些重复的东西。既然有重复那我就把这些重复算的东西用一个数组保存起来要用时就不用再去算一遍只要调用了。所以把时间复杂度大大提升了只有O(n2)了。 1 #include stdio.h2 #include math.h3 #include string.h4 int map[101][101],book[101][101];5 int n;6 int max(int x,int y){7 if(yx)8 return y;9 else
10 return x;
11 }
12 int search(int r,int c){
13 int ans;
14 if (rn) return map[r][c];
15 if (book[r1][c]-1)
16 book[r1][c]search(r1,c);
17 if (book[r1][c1]-1)
18 book[r1][c1]search(r1,c1);
19 ansmax(book[r1][c],book[r1][c1])book[r][c];
20 return ans;
21 }
22 int main(){
23 scanf(%d,n);
24 int i,j;
25 for(i1;in;i){
26 for(j1;ji;j){
27 scanf(%d,map[i][j]);
28 book[i][j]-1;
29 }
30 }
31 printf(%d,search(1,1));
32 return 0;
33 } View Code 思路代码(动态规划) 自底向上。第i层的任意一个点其最大值是它自己加上它下一层的两个点的最大值之和。用i表示行j表示列状态转移方程如下。这样时间复杂度也只有O(2n)。 1 #include stdio.h2 #include math.h3 #include string.h4 int map[101][101],book[101][101];5 int max(int x,int y){6 if(xy)return x;7 else return y;8 }9 int main(){
10 int n;
11 scanf(%d,n);
12 int i,j;
13 for(i1;in;i){
14 for(j1;ji;j){
15 scanf(%d,map[i][j]);
16 }
17 }
18 for(j1;jn;j)
19 book[n][j]map[n][j];
20 for(in-1;i1;i--)
21 for(j1;ji;j)
22 book[i][j]max(book[i1][j1],book[i1][j])map[i][j];
23 printf(%d,book[1][1]);
24 return 0;
25 } View Code 2.最长上升子序列 思路 对于以第i个数为右端点的一个序列他本身就是一个长度为1的上升子序列。这时如果它的右边有比它数值更小的数这时的最长上升子序列就是这个元素本身的长度1和以他前面的比他数值更小的这个元素为右端点的最长上升子序列的长度和。 状态转移方程sum[i]_Max(sum[i],sum[j]1); (jinum[j]num[i]) 核心代码 1 sum[1]1;2 for(i2;in;i){3 sum[i]1;4 for(j1;ji;j){5 if(num[j]num[i]){6 sum[i]_Max(sum[i],sum[j]1);7 }8 }9 }
10 for(i1;in;i)
11 max_Max(max,sum[i]); View Code 状态AC转载于:https://www.cnblogs.com/yzyl-Leo-wey/p/8167768.html
