国外校友网站建设的现状,wordpress 4.7.3 乱码,网站运维平台建设原则,厦门网站建设公司排行榜给定一个如下图所示的数字三角形#xff0c;从顶部出发#xff0c;在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点#xff0c;一直走到底层#xff0c;要求找出一条路径#xff0c;使路径上的数字的和最大。 73 88 1 02 7 4 4
4 5 2 6 …给定一个如下图所示的数字三角形从顶部出发在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点一直走到底层要求找出一条路径使路径上的数字的和最大。 73 88 1 02 7 4 4
4 5 2 6 5输入格式
第一行包含整数 n表示数字三角形的层数。
接下来 n 行每行包含若干整数其中第 i 行表示数字三角形第 i 层包含的整数。
输出格式
输出一个整数表示最大的路径数字和。
数据范围
1≤n≤500, −10000≤三角形中的整数≤10000
输入样例
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5输出样例
30
思路在分析状态集合的时候可以发现如果f(i,j)是自顶向下遍历那就有很多边界问题需要处理因为下一层的f(i,j)可以由f(i-1,j-1)和f(i-1,j)递推。而如果是自底向上遍历就不需要考虑边界问题。这里是因为自底向上是层数越来越小不需要考虑边界自顶向下层数越来越大需要考虑边界 完整代码很简洁
#include iostream
using namespace std;
const int N510;
int dp[N][N];
int main(){int n;cinn;for(int i1;in;i)for (int j1;ji;j)cindp[i][j];for (int in-1;i;i--) {for (int j 1; j i; j){dp[i][j]max(dp[i1][j],dp[i1][j1]);}}coutdp[1][1];
}
带注释
#include iostream
using namespace std;const int N 510; // 定义常量 N 为 510表示数字三角形的最大层数int dp[N][N]; // 定义二维数组 dp用于存储动态规划中的状态值int main() {int n; // 声明变量 n用于存储数字三角形的层数cin n; // 读取输入的层数// 循环读取输入的每一行数据并存储到二维数组 dp 中for (int i 1; i n; i)for (int j 1; j i; j)cin dp[i][j];// 动态规划求解从倒数第二行开始向上递推for (int i n - 1; i 1; i--) {for (int j 1; j i; j) {// 状态转移方程dp[i][j] 表示第 i 行第 j 列位置的最大路径和// 更新 dp[i][j] 为当前位置值加上下一行相邻两个位置中的较大值dp[i][j] max(dp[i 1][j], dp[i 1][j 1]);}}// 输出结果即在第一行第一列的位置上的最大路径和cout dp[1][1];return 0;
}
