动态规划

顺推

• 推演过程：
  • 13 ====>13
  • 11 8 ====>24 21
  • 12 7 26 ====>36 31 47
  • 6 14 15 8 ====>42 50 62 55
  • 12 7 13 24 11 ====>54 57 75 86 66

完整代码

#include<bits/stdc++.h>   
#define ll long long
using namespace std;
ll n,num[1005][1005];
ll cnt[1005][1005],ans;  
int main()
{
    std::ios::sync_with_stdio(false);
    memset(num,0,sizeof(num));//本题使用动态规划
    memset(cnt,0,sizeof(cnt));//顺推
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            cin>>num[i][j];
    cnt[1][1]=num[1][1];
    for(int i=2;i<=n;i++)//状态转化 
        for(int j=1;j<=i;j++)
            cnt[i][j]=num[i][j]+max(cnt[i-1][j-1],cnt[i-1][j]);

    for(int i=1;i<=n;i++){//找最大 
        if(ans<cnt[n][i])
            ans=cnt[n][i]; 
    }
    cout<<ans;
    return 0;
}

逆推

• 推演过程：
  • 13 ====>86
  • 11 8 ====>57 73
  • 12 7 26 ====>39 46 65
  • 6 14 15 8 ====>18 27 39 32
  • 12 7 13 24 11 ====>12 7 13 24 11

for(int i=1;i<=n;i++)
    cnt[n][i]=num[n][i];
for(int i=n-1;i>=1;i--){
    for(int j=1;j<=i;j++)
        cnt[i]][j]=num[i][j]+max(cnt[i-1][j-1],cnt[i-1][j]);
}
cout<<cnt[1][1];//cnt[1][1]为最大

在逆推的基础上可以用一维数组进行空间优化

• 推演过程:
  • 86 73 65 32 11
  • 57 73 65 32 11
  • 39 46 65 32 11
  • 18 27 39 32 11
  • 12 7 13 24 11

#include<bits/stdc++.h>   
#define ll long long
using namespace std;
ll n,num[1005][1005];
ll cnt[1005],ans; 
int main()
{
    std::ios::sync_with_stdio(false);
    memset(num,0,sizeof(num));
    memset(cnt,0,sizeof(cnt));
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            cin>>num[i][j];
    for(int i=1;i<=n;i++)//先将最后一组数据赋给cnt
        cnt[i]=num[n][i];
    for(int i=n-1;i>=1;i--)
        for(int j=1;j<=i;j++)
            cnt[j]=num[i][j]+max(cnt[j],cnt[j+1]);
    cout<<cnt[1];
    return 0;
}

我相信不少人，第一反应 肯定是 DFS 吧，所以 在这里 把 DFS 和 DP 的代码 都奉上。当然 单纯的 DFS 是过不了的。会超时！

#include <iostream>
#include <algorithm>

using namespace std;

int maxSum = 0;
int sum = 0;
int arr[1005][1005];
bool vis[1005][1005];
int R;

int off[2][2] = { {1,0},{1,1} };
int dp[1005][1005];

void dfs11(int x,int y) {
	if (vis[x][y]) {
		return;
	}
	else {
		vis[x][y] = true;
		sum += arr[x][y];
	}
	if (x == R) {// 已经走到了 最底部
		if (maxSum < sum) {
			maxSum = sum;
		}
		return;
	}

	for (int i = 0; i < 2; ++i) {
		int tempX = x + off[i][0];
		int tempY = y + off[i][1];
		if (tempY > tempX) {
			continue;
			
		}
		dfs11(tempX, tempY);
		vis[tempX][tempY] = false;
		sum -= arr[tempX][tempY];
	}

}

int main(void) {
	
	cin >> R;
	for (int i = 1; i <= R; ++i) {
		for (int j = 1; j <= i; ++j) {
			cin >> arr[i][j];
		}
	}

	//dfs11(1, 1);// 从 第一行 第一列 开始 走
	//dp[i][j] = dp[i-1][j] 
	for (int i = 1; i <= R; ++i) {
		for (int j = 1; j <= i; ++j) {
			if (j == 0) {
				dp[i][j] = dp[i - 1][j] + arr[i][j];// 只有一种选择
			}
			else if (j == i) {
				dp[i][j] = dp[i - 1][j - 1] + arr[i][j]; // 只有一种选择
			}
			else {
				dp[i][j] = max(dp[i - 1][j - 1], dp[i-1][j]) + arr[i][j];
			}
		}
	}

	for (int i = 1; i <= R; ++i) {
		maxSum = max(maxSum, dp[R][i]);
	}


	cout << maxSum << endl;

	return 0;
}

我支持春哥

#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
using ll = long long;
const int N = 1e3+10;
ll a[N][N],sum;
int main()
{
    ll sum = 0;
   int r;cin>>r;
   for(int i = 1;i <= r;i++)
   {
        for(int j = 1;j <= i;j++)
        {
            cin>>a[i][j];
        }
   }

   for(int i = 2;i <= r;i++)
   {
        for(int j = 1;j <= i;j++)
        {
            //一定要注意考虑边界值
            if(j == 1)
            {
                a[i][j] += a[i-1][j];
            }
            else if(j == i)
            {
                a[i][j] += a[i-1][j-1];
            }
            else 
            {
                a[i][j] += max(a[i-1][j],a[i-1][j-1]);
            }
        }
        
   }
   for(int j = 1; j <= r;j++)
   {
        sum = max(sum,a[r][j]);
   }
   cout<<sum<<"\n";
    return 0; 
}

#include <bits/stdc++.h>
using namespace std;
int ma[1010][1010];
int sum[1010][1010];

int main()
{
	int r;
	cin>>r;
	for(int i=1;i<=r;i++)
	{
		for(int j=1;j<=i;j++) cin>>ma[i][j];
	}
	for(int i=1;i<=r;i++)
	{
		for(int j=1;j<=i;j++)
		{
			sum[i][j]=ma[i][j]+max(sum[i-1][j],sum[i-1][j-1]);
		}
	}
	cout<<*max_element(sum[r]+1,sum[r]+1+r);
}

DFS 记忆化搜索

#include <bits/stdc++.h>
using namespace std;

#define DBG(x) cout << #x << "=" << x << endl

const int N = 1005;
int n, a[N][N], f[N][N];

int dfs(int x, int y) {
  // 查缓存，记忆化
  if (f[x][y] != -1)
    return f[x][y];
  // 边界：最后一行
  if (x == n)
    return f[x][y] = a[x][y];
  // 记忆化搜索
  return f[x][y] = max(dfs(x + 1,y), dfs(x + 1, y + 1)) + a[x][y];
}

void solve() {
  scanf("%d", &n);
  for(int i = 1; i <= n; i++)
    for(int j = 1; j <= i; j++)
      scanf("%d", &a[i][j]);

  memset(f, -1, sizeof f);
  dfs(1, 1);
  printf("%d\n", f[1][1]);
}

int main() {
  solve();

  return 0;
}

动态规划，来看我的。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
//dp[i][j]//i:高度，j：位置
/*
dp[i][j] = max(dp[i+1][j],dp[i+1][j]) + w[i][j]

 */
const int N = 1e3+10;
int w[N][N]; //每个点的权值
LL dp[N][N]; //存储每个点及以下的权值和
int main(){
	int R;
	cin>>R;
	for(int i=1;i<=R;i++){
		int j=i;
		for(int j=1;j<=i;j++){
			int c;
			cin>>c;
			w[i][j] = c;
		}
	}
	for(int i=R;i>=1;i--){
		for(int j=1;j<=i;j++){
			if(i==R){
				dp[i][j]=w[i][j];
			}
			else{
				dp[i][j] = max(dp[i+1][j],dp[i+1][j+1]) + w[i][j];
			}
		}
	}
	cout<<dp[1][1]<<endl;
	return 0;
}

emm....雀食是个动态规划的模板题，直接上代码吧

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<cstring>

using namespace std;
int num[1005][1005];
int main(void)
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int k=1;k<=i;k++) cin>>num[i][k];//输入
		
	for(int i=1;i<=n;i++)
		for(int k=1;k<=i;k++) num[i][k]=max(num[i][k]+num[i-1][k],num[i][k]+num[i-1][k-1]);//想象成把数层层往下加，一直加到最后一层
	
	int ans=0;
	for(int i=1;i<=n;i++) ans=max(ans,num[n][i]);//比较最后一层哪个最大输出即可
	
	cout<<ans; 
	
	
	return 0;
}