#include "pch.h"
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
int main()
{
int n;
cin >> n;
//int arr[n + 1][n + 1];
//int res[n + 1][n + 1];错误
//vs定义二维数组要用以下方法
//联系一维数组理解,int* n1Arr = new int[rows];
int** arr = new int* [n + 1];
for (int i = 0; i < n + 1; i++)
{
arr[i] = new int[n + 1];
}
int** res = new int* [n + 1];
for (int i = 0; i < n + 1; i++)
{
res[i] = new int[n + 1];
}
memset(arr[0], -1, sizeof(int)*(n + 1));//第0行初始化为-1
memset(res[0], -1, sizeof(int)*(n + 1));
for (int i = 1; i <= n; i++) {//数字三角初始化
for (int j = 1; j <= i; j++) {
cin >> arr[i][j];
}
}
// 初始化res结果数组
for (int i = 1; i <= n; i++) {
res[n][i] = arr[n][i];
}
for (int i = n - 1; i >= 1; i--) {
for (int j = 1; j <= i; j++) {
// 动规填表
res[i][j] = max(res[i + 1][j], res[i + 1][j + 1]) + arr[i][j];
}
}
/*
// 打印res数组
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
cout << res[i][j] << " ";
}
cout << endl;
}
cout << endl;
*/
cout << res[1][1] << endl;//最大路径和值
// 找出靠右路径
int y = 1;
cout << arr[1][y] << " ";//顶部最大
for (int i = 2; i <= n; i++) {
// 从上往下找,只需要比较 y 和 y+1,相应输出 “最大值下标对应的” 原值
if (res[i][y] <= res[i][y + 1]) {
cout << arr[i][y + 1] << " ";
y = y + 1;//更新y
}
else {
cout << arr[i][y] << " ";
}
}
return 0;
}
/*
5
7
3 8
8 1 6
2 7 4 4
4 5 2 4 5
30
7 3 8 7 5
假设a[i, j]表示数塔中从上到下第i层,从左向右第j个数的数值,
且设m[i, j]表示数塔从上到下第i层,从左向右第j个数所具有的最大路径和的值。那么就有如下递推的式子:
m[i,j]= a[i,j] i=n
max{m[i+1,j],m[i+1,j+1]}+a[i,j] 1<=i<n
*/
没有合适的资源?快使用搜索试试~ 我知道了~
10303 数字三角(dp).zip_4 3 2 1_quietvzi_yourselfy63_算法
共26个文件
tlog:6个
pdb:2个
cpp:2个
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 169 浏览量
2022-09-15
01:34:27
上传
评论
收藏 2.34MB ZIP 举报
温馨提示
Description 问题描述:给定一个由n行数字组成的数字三角形,如下图所示。试用动态规划算法,计算出从三角顶部至底部的一条路径,使得该路径经过的数字总和最大。 注意每个数字只能走向下一行左边或右边的数字,而不能跳跃的走。 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 输入格式 第一行是数字三角的行数n,1<=n<=100。接下来n行是数字三角各行中的数字,所有数字在0~99之间。 输出格式 输出两行,第一行是计算出的最大路径的和值,第二行是该路径上的数字。若有多条路径,靠右的路径优先(即仅仅输出靠右的路径即可,无需多条路径都输出)。 如: Input: 5 7 3 8 8 1 6 2 7 4 4 4 5 2 4 5 有两条路径:7-3-8-7-5和7-8-6-4-5都为30,由于后者靠右,因此仅输出后者。 Output: 30 7 8 6 4 5 输入样例 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
资源详情
资源评论
资源推荐
收起资源包目录
10303 数字三角(dp).zip (26个子文件)
10303 数字三角(dp)
.vs
10303 数字三角(dp)
v15
Browse.VC.db 5.27MB
.suo 27KB
ipch
a56cdb183b20ee5b.ipch 320KB
10303 数字三角(dp).sln 1KB
10303 数字三角(dp)
10303 数字三角(dp).vcxproj.user 165B
pch.h 614B
10303 数字三角(dp).vcxproj.filters 1KB
10303 数字三角(dp).vcxproj 8KB
10303 数字三角(dp).cpp 3KB
pch.cpp 188B
Debug
10303 数字三角(dp).obj 60KB
pch.obj 4KB
10303 数字三角(dp).log 189B
vc141.idb 147KB
10303 数字三角(dp).tlog
10303 数字三角(dp).lastbuildstate 249B
CL.write.1.tlog 1KB
CL.read.1.tlog 16KB
CL.command.1.tlog 2KB
link.write.1.tlog 640B
link.command.1.tlog 1KB
link.read.1.tlog 3KB
vc141.pdb 356KB
10303 数字三角(dp).pch 1.94MB
Debug
10303 数字三角(dp).pdb 508KB
10303 数字三角(dp).exe 53KB
10303 数字三角(dp).ilk 414KB
共 26 条
- 1
小贝德罗
- 粉丝: 68
- 资源: 1万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0