zjh

```cpp
思路1：首先想，如果我们从上往下枚举，那么就相当于遍历了整棵树，等价于dfs，每条路都去试一遍，取得一个最大值，那么这个效率是不够高的，所以我们要想一种效率比较高的算法，可以发现，A[i][j] 作用于 A[i + 1][j] 和 A[i + 1][j + 1]这个关系，那么不难想，A[i + 1][j] 和 A[i + 1][j + 1]决定着A[i][j]，可以倒着想，如果从最后一行开始往上走，会是什么效果呢？
假设现在n = 2
1
2 3
答案肯定是4
我们从最后一行开始，对每一个j, j + 1进行max得到一个最大值
2 3 自然是 3 > 2， 刚才说了，A[i + 1][j] 和 A[i + 1][j + 1] 决定着A[i][j]
那么这里就可以得出 A[1][1] = max(A[2][1], A[2][2]) + A[1][1];
初始化：i = n, j = 1.....n;  f[i][j] = A[i][j];
转移方程：f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + A[i][j];

这里使用了滑动窗口，因为我们已经发现了f[i][j] 依赖于 f[i + 1][j] 和 f[i + 1][j + 1] i, j 只依赖于它的正下方和右下方，所以我们从1....j枚举的过程中产生的新结果j并不会对j + 1原有的结果造成影响，从而当j = j + 1后，它依赖的 j 和 j + 1 并没有发生改变
详细请看代码

#include "iostream"
#include "cstdio"
#include "cstdlib"
#include "cstring"
#include "cmath"
#include "algorithm"
#include "queue"
#include "vector"
#include "stack"
#include "map"
#include "set"
using namespace std;
typedef long long ll;
const int maxn = 110;
const int INF = 1e9;

int n, A[maxn][maxn], dp[maxn];

int main() {
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= i; ++j) {
			cin >> A[i][j];
			dp[j] = A[i][j];	//直接放在输入里初始化了，前面的会覆盖，最后保存的是A[n][1....n]的值
		}
	}
	//从倒数第二行开始向上走
	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];	//转移方程
		}
	}
	//最后答案就是dp[1]，从下往上走到头的地方
	cout << dp[1] << endl;
	return 0;
}

思路2：我们可以从上往下走，每次输入，我们更新每个j的值就可以了，然后保存最大值就是答案，同样利用滑动窗口，只不过这次的j需要从后往前避免覆盖

int n, dp[maxn];

int main() {
	cin >> n;
	int res = 0;	//用来记录结果最大值
	//从n......1滑动
	for(int i = n; i >= 1; --i) {
		for(int j = i; j <= n; ++j) {
			int x;	//不用再开一个A[n][n]的数组存数据，可以直接在输入时处理
			cin >> x;
			dp[j] = max(dp[j], dp[j + 1]) + x;
			res = max(res, dp[j]);
		}
	}
	cout << res << endl;
	return 0;
}

```

0.0分

6 人评分

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

zjh

TA的其他文章

你可能喜欢

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

C语言程序设计教程（第三版）课后习题6.2 （C++代码）为什么回车不算字符

printf基础练习2 （C语言代码）

【明明的随机数】（C语言代码）

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

蓝桥杯算法提高VIP-夺宝奇兵（C++代码）dp + 滑动窗口

评论区

精彩推荐

数列排序（C语言代码）

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

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

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

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

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

数字游戏（C++代码）

1050题解（结构体数组与结构体指针的使用）

C二级辅导-分段函数（C语言代码）

Hello, world! （C语言代码）

zjh

TA的其他文章

你可能喜欢

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

C语言程序设计教程（第三版）课后习题6.2 （C++代码）为什么回车不算字符

printf基础练习2 （C语言代码）

【明明的随机数】 （C语言代码）

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

蓝桥杯算法提高VIP-夺宝奇兵 （C++代码）dp + 滑动窗口

评论区

精彩推荐

数列排序 （C语言代码）

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

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

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

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

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

数字游戏 （C++代码）

1050题解（结构体数组与结构体指针的使用）

C二级辅导-分段函数 （C语言代码）

Hello, world! （C语言代码）

【明明的随机数】（C语言代码）

蓝桥杯算法提高VIP-夺宝奇兵（C++代码）dp + 滑动窗口

　　评论区

数列排序（C语言代码）

数字游戏（C++代码）

C二级辅导-分段函数（C语言代码）