1.先来看看这题你有思路吗
你想怎么做呢
拿到这题，你是不是想用贪心或者其他的？
当然，你可以直接dfs(那叫一个酸爽~)
好下面,我们从这题开始来讲dp
2.先推样例(你懂的)
它先输入层数，然后输入数塔，输进去之后，你懂的，他并不是题目给的图片的样子，而是这样:
13
11 8
12 7 26
6 14 15 8
12 7 13 24 11
好了，在此之前，你肯定读过了题目，否则再读一遍,要不然你怎么做题?
那么，你肯定读完了，来算算吧
...
...
经过你的漫长计算，你可能得出了正确的答案:86，没错那是怎么来的呢？没错从13到8到26到15到24!
聪明的你肯定发现了,如果你用贪心,每次选最大的,那么你会错失那最大的26(因为只能那样和那样走啦,所以你不知道是怎样,那么再读一遍,要不然你怎么做题?).所以，聪明的程序员们就发明了一种算法——dp
3.dp介绍
DP(有点重要，之后会折磨你的),中文是动态规划.
那么what is dp？
用人话讲就是dp的前几个状态经过一些乱七八糟的计算，从而得到当前状态
4.你们的题解终于到了
在样例中,它是一种直角三角形,所以每次只能走下面的、右下方的(在这里，你还没读题的话,孩子,你可以退出这个文章了),之前提到，对于当前状态，要对前面的进行一些操作，才能得到，那么也就是说,我的dp[i][j]是前面的max(dp[i-1][j],dp[i-1][j-1])+a[i][j]得到的,顺便提一下:
1.dp一定要从1开始，你不听，哎，那就试试就逝世
2.刚才max的那个式子叫做动态转移方程
好现在你们会写了吧
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int dp[N][N],a[N][N];
int n;
//接下来我只写思路,但dp部分会写
int main(){
cin>>n;
//输入
for(int xxx){
for(int xxx){
cin>>xxx;
}
}
dp[1][1]=a[1][1];//初始化
for(int xxx){
for(int xxx){
dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j];//刚才的转移方程
}
}
//找最大值
for(int xxx){
//由于最后的值都在底部，所一直用便利列
mx=max(mx,xxx);
}
cout<<mx;
return 0;
}
作为一个三四段的小朋友，输入输出找最大值你都不会的话,我是真要找无量仙翁要个天元鼎把你给炼了。(语言过于虚幻）
5.做完那题请完成以下习题
6.初级dp第一回合总结
dp最重要的是转移方程，这个东西基本上要考脑子，不需要写太多代码(到时候dp就真的变了QWQ)
(i一定要从1开始!)*114514
2 条评论
-
！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
-
@ 2025-3-14 21:03:49？
-
@ 2025-4-6 22:03:23
#include<bits/stdc++.h> using namespace std; const int N=1010; int dp[N][N],a[N][N]; int n; int main(){ cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=i;j++){ cin>>a[i][j]; } } dp[1][1]=a[1][1]; for(int i=2;i<=n;i++){ for(int j=1;j<=i;j++){ if(j == 1) { dp[i][j] = dp[i-1][j] + a[i][j]; } else if(j == i) { dp[i][j] = dp[i-1][j-1] + a[i][j]; } else { dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + a[i][j]; } } } int mx = 0; for(int j=1;j<=n;j++){ mx = max(mx, dp[n][j]); } cout<<mx; return 0; }do you mean this?
-
- 1