我是靠谱客的博主 直率老虎,这篇文章主要介绍dp数塔问题和矩阵取数问题 ,现在分享给大家,希望可以做个参考。

Dp问题-----本文写两个经典dp问题,思路相同

如有问题,请大佬指教~撒花撒花~

 一.数塔问题:(题目在下方)

思路:

dp[i][j]=======>存储

a[i][j]========>输入的数组

我们在输入时,数塔则成下图的形状,我们把他想象成数组,行设为i,列为j,并且可以看出只能向下和右下两个方向,但我们从下向上。

列出:

dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j]

 

代码:

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<cstdio> #include<iostream> using namespace std; #include<cmath> #include<cstring> int main() { int C,N; int dp[101][101]; int a[101][101]; memset(a,0,sizeof(a)); memset(dp,0,sizeof(dp)); scanf("%d",&C); while(scanf("%d",&N)){ for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { scanf("%d",&a[i][j]); } } } dp[1][1]=a[1][1]; for (int i = 1; i <= N; i++) { for (int j = 1; j <=N; j++) { dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j]; } } int ans = 0; for (int i = 1; i <= N; i++) { ans = max(dp[N][i], ans); } printf("%d",ans); return 0; }

二.矩阵取数问题:(题目下方)

思路和上一个一样,直接在下面贴代码了

 

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<cstdio> #include<iostream> using namespace std; #include<cmath> #include<cstring> int main() { int dp[1001][1001]; int a[1001][1001]; memset(a,0,sizeof(a)); memset(dp,0,sizeof(dp)); int N; while(scanf("%d",&N)!=EOF) { for(int i=1;i<=N;i++) { for(int j=1;j<=N;j++) { scanf("%d",&a[i][j]); } } } for(int i=1;i<=N;i++) { for(int j=1;j<=N;j++) { dp[i][j]=max(dp[i][j-1],dp[i-1][j])+a[i][j]; } } dp[1][1]=a[1][1]; int ans=0; for(int i=1;i<=N;i++) { ans=max(ans,dp[N][i]); } printf("%d",ans); }

 

最后

以上就是直率老虎最近收集整理的关于dp数塔问题和矩阵取数问题 的全部内容,更多相关dp数塔问题和矩阵取数问题 内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(190)

评论列表共有 0 条评论

立即
投稿
返回
顶部