这题是道动规题因为标签是动规...啊啊啊放错了

这题是求从起点到终点的最大路径,每个点不受其它点的影响,无后效性,所以是动态规划题。(这才对嘛

• 首先确定dp数组含义,这里dp[i]含义是从起点到i点的最大路径和。
• 其次确定状态转移方程,dp[i][j]可由dp[i-1][j]或dp[i-1][j-1]得到。于是我们的状态转移方程为:dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - 1]) + a[i][j];。
• 再次是初始化,dp[1][1]=a[1][1],dp数组中其它的不用初始化,等于什么都可以。
• 最后是遍历顺序,按题目中说的二维三角形来。
• 众所周知,节俭是个好习惯,所以我们的dp数组和a数组只用开25*25!

蒟蒻の代码:

#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;

int dp[1001][1001],a[1001][1001],ans,n;

int main()
{
    int n;
    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 = 1;i <= n;i++)
    {
        for(int j = 1;j <= i;j++)
        {
            dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - 1]) + a[i][j];//转移方程
            ans = max(ans,dp[i][j]);
        }
    }
    cout << ans;
    return 0;
}

这题!也可以用递归做!🙂

代码:

#include <iostream>
using namespace std;

bool is[1001][1001];
int a[1001][1001],f[1001][1001],n,ans;

int dfs(int x,int y)
{
	if(x == 1)
	{
		return a[1][1];
	}
	if(is[x][y])
	{
		return f[x][y];
	}
	is[x][y] = true;
	f[x][y] = max(dfs(x - 1,y),dfs(x - 1,y - 1)) + a[x][y];
	
	return f[x][y];
}
int main()
{
    cin >> n;
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= i;j++)
		{
			cin >> a[i][j];
		}
    }
    for(int i = 1;i <= n;i++)
    {
        ans = max(ans,dfs(n,i));
    }
    cout << ans;
    return 0;
}

经典动态规划题，递归思考，递推解决。

太经典，不做解释。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int a[N][N];
int dp[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
	for(int i=n;i>=1;i--)
	{
		for(int j=1;j<=i;j++)
		{
			dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j];
		}
	}
	cout<<dp[1][1];
	return 0;
}

using namespace std;
int x,y,a[1001][1001];
int main(){
	cin >> x;
	for(int i = 1 ; i <= x ; i++){
		for(int j = 1 ; j <= i ; j++) cin >> a[i][j];
	}
	for(int i = 1 ; i <= x ; i++){
		for(int j = 1 ; j <= i ; j++) a[i][j] += max(a[i-1][j],a[i-1][j-1]);
	}
	for(int i = 1 ; i <= x ; i++){
		y = max(y,a[x][i]);
	}
	cout << y << endl;;
}

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <math.h>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <stack>

using namespace std;

#define LL long long
const int N =1e5+10;
const int INF =0x3f3f3f3f;
int a[3000][3000];
int r,ans;
int main(){
	cin>>r;
	for(int i=1;i<=r;i++){
		for(int j=0;j<i;j++){
			cin>>a[i][j];
			a[i][j]+=max(a[i-1][j],a[i-1][j-1]);
			ans=max(ans,a[i][j]);
		}
	}
	cout<<ans<<endl;
	return 0;
}

#include<iostream> using namespace std; int n,a[1001][1001],maxn; int main() { cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=i;j++){ cin>>a[i][j]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=i;j++){ a[i][j]+=max(a[i-1][j],a[i-1][j-1]); } } for(int i=1;i<=n;i++){ maxn=max(maxn,a[n][i]); } cout<<maxn; }

#include<iostream> using namespace std; int n,a[1001][1001],maxn; int main() { cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=i;j++){ cin>>a[i][j]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=i;j++){ a[i][j]+=max(a[i-1][j],a[i-1][j-1]); } } for(int i=1;i<=n;i++){ maxn=max(maxn,a[n][i]); } cout<<maxn; }

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e3 + 10; 
int a[N][N];
int main(){
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= i; j++){
			cin >> a[i][j];
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= i; j++){
			a[i][j] = max(a[i-1][j-1], a[i-1][j]) + a[i][j];
		}
	}
	int maxx = 0;
	for(int i = 1; i <= n; i++){
		maxx = max(maxx, a[n][i]);
	}
	cout << maxx << endl;
}