首页 > 代码库 > 一天一道算法题--5.29---动态规划之数塔

一天一道算法题--5.29---动态规划之数塔

2024-07-06 10:07:25   224人阅读

感谢微信平台：  一天一道算法题-------每天多一点进步-----------

这题的话 我就直接用我们自己Oj的题目了

                       戳我

好吧  如今看这题  是很简单  当时 是块被它搞崩溃了   因为 还不知道  dp 这个概念

现在有了这个概念   好多了  但还是 只能做做这种水 dp。。。。

多么悲伤的故事

这题 因为太水了   晚上 应该会去找个高质量的题来做的

如果你是dp刚刚学 这题真的很适合你

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int size = 110;
 7 int dp[size][size];
 8 
 9 int main()
10 {
11     int t;
12     int n;
13     int i , j;
14     while( ~scanf("%d",&t) )
15     {
16         while( t-- )
17         {
18             memset( dp , 0 , sizeof(dp) );
19             scanf( "%d",&n );
20             for( i = 1 ; i<=n ; i++ )
21             {
22                 for( j = 1 ; j<=i ; j++ )
23                 {
24                     scanf( "%d",&dp[i][j] );
25                 }
26             }
27             //采用 自底向上的方法进行计算
28             for( i = n-1 ; i>=1 ; i-- )
29             {
30                 for( j= 1 ; j<=i ; j++ )
31                 {
32                     dp[i][j]+=max( dp[i+1][j] , dp[i+1][j+1] );
33                 }
34             }
35             printf( "%d\n",dp[1][1] );
36         }
37     }
38     return 0;
39 }
View Code

我们Oj还有个加强版的数塔题  也就是 多增加个输出路径罢了

这边 也给出它的链接     touch  me

至于它的代码 我就先不给出了   这题 还是蛮有意思的   让我想起了一些关于bfs的打印路径 就是一个father数组

 

 

 

 

 


联系
我们