HzuQZH

用户名：h1810819001

访问量：32318

签　名：

等　　级
排　　名	45
经　　验	12276
参赛次数	7
文章发表	69
年　　龄	0
在职情况	学生
学　　校	贺州学院
专　　业

　　自我简介：

TA的其他文章

数据结构-KMP字符串模式匹配算法实现-题解(C++代码)
浏览：504

数据结构-用数组实现堆排（易处理，容易理解）
浏览：634

区间dp（动归思想）
浏览：938

你可能喜欢

A+B for Input-Output Practice (II) （C语言代码）

小白可看!!!dp算法入门——数字三角形

　　作者: HzuQZH　　　　发表时间：2019-10-28 20:28:32 浏览：280　|　评论：0　

原题链接：三角形

安利一发自己的博客：我是蒟蒻，请轻喷。
[https://blog.csdn.net/weixin_43738764](https://blog.csdn.net/weixin_43738764)
解析：
	**dp算法的重点在于：要知道他是怎么样的状态，并且是怎么样从前面那个转移过来的，个人看法是可以理解为从上一步到当前步我应该做些什么，dp算法难度在于思维。**
	
	题目分析：
		dp[i][j]表示从（1，1）这个起点开始，到（i，j）的最大和。
		这个题目应该属于dp算法入门题，可以从样例看出和题目看出，从第二行开始，每一个位置加上的数，只会是它正上方的数或者右上方的数。
		因此转移方程为：dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+w[i][j]。这里的意思是上方和右上方的数比较取最大一个加到本事。

```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+7,inf=0x3f3f3f3f;
int w[N][N],dp[N][N];//dp存放的是从起点到当前位置最大和，w是权值
int main(){
    int n,t;
    cin>>t;
    while(t--){
        memset(dp,-inf,sizeof dp);//开始给全部的和极大负值，方便后面处理
        cin>>n;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=i;j++){
                cin>>w[i][j];
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=i;j++){
                if(i==1&&j==1)dp[i][j]=w[i][j];//第一个起点不用处理，最大和就是本身
                else{//如果之前不给dp全部赋值为极大负值，如果当前值为赋值，就会和越界点（权值为0）的比较，肯定会选择0导致最后错误
                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+w[i][j];//状态转移
                }
            }
        }
        int ans=-1e9;
        for(int i=1;i<=n;i++)ans=max(ans,dp[n][i]);
        cout<<ans<<endl;
    }
    return 0;
}

```

## 这个算法还可以进行空间优化，不是重点，不进行解析自行了解即可。

```cpp
//上面的代码至上而下，这个空间优化代码至下而上，自行了解
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int>Pall;
namespace IO{
    inline LL read(){
        LL o=0,f=1;char c=getchar();
        while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
        while(c>='0'&&c<='9'){o=o*10+c-'0';c=getchar();}
        return o*f;
    }
}using namespace IO;
const int N=507,INF=0x3f3f3f3f;
int a[N][N],dp[N];
int main(){
    int n,t;
    cin>>t;
    while(t--){
        cin>>n;
        memset(a,-INF,sizeof a);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=i;j++){
                cin>>a[i][j];
                dp[j]=a[i][j];
            }
        }
        for(int i=n-1;i>=1;i--){
            for(int j=1;j<=i;j++){
                dp[j]=max(dp[j],dp[j+1])+a[i][j];
            }
        }
        cout<<dp[1]<<endl;
    }
    return 0;
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

HzuQZH

TA的其他文章

你可能喜欢

A+B for Input-Output Practice (II) （C语言代码）

用筛法求之N内的素数。（C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

程序员的表白（C语言代码）

简单的a+b （C语言代码）

小白可看!!!dp算法入门——数字三角形

评论区

精彩推荐

母牛的故事（C语言代码）

C二级辅导-公约公倍（C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

GC的苦恼（C语言代码）

剪刀石头布（C语言代码）

C语言训练-大、小写问题（C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

【魔板】（C++代码）

平方数问题，oj一直是wrong answer

HzuQZH

TA的其他文章

你可能喜欢

A+B for Input-Output Practice (II) （C语言代码）

用筛法求之N内的素数。 （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

程序员的表白 （C语言代码）

简单的a+b （C语言代码）

小白可看!!!dp算法入门——数字三角形

评论区

精彩推荐

母牛的故事 （C语言代码）

C二级辅导-公约公倍 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

GC的苦恼 （C语言代码）

剪刀石头布 （C语言代码）

C语言训练-大、小写问题 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

【魔板】 （C++代码）

平方数问题，oj一直是wrong answer

用筛法求之N内的素数。（C++代码）

程序员的表白（C语言代码）

　　评论区

母牛的故事（C语言代码）

C二级辅导-公约公倍（C语言代码）

GC的苦恼（C语言代码）

剪刀石头布（C语言代码）

C语言训练-大、小写问题（C语言代码）

【魔板】（C++代码）