数字三角形 (DP入门)
2024-10-07 17:21:21
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
给出一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,你的任务就是找到最大的和。
注意:路径上的每一步只能从一个数走到下一层上和它最近的左边的那个数或者右边的那个数
输入
第一行是一个整数N (1 < N <= 100),给出三角形的行数。
下面的N行给出数字三角形。数字三角形上的数的范围都在0和100之间。
输出
输出最大的和。
Sample input
- 5
- 7
- 3 8
- 8 1 0
- 2 7 4 4
- 4 5 2 6 5
sample input
- 30
dp入门第一题
#include<bits/stdc++.h>
using namespace std;
int a[][];
int d[][];
int n;
int F(int i,int j)//记忆化递归
{
if(d[i][j]>=) return d[i][j];
return d[i][j] = a[i][j] + (i == n ? : max(F(i+,j),F(i+,j+)));
}
int main()
{
memset(d,-,sizeof(d));
cin >>n;
for(int i=;i<=n;i++)
for(int j=;j<=i;j++)
cin >> a[i][j];
cout << F(,) << endl;
return ;
}
代码
最新文章
- JTabbedPane 和 JScrollBar 联合使用
- Eclipse svn插件包
- linux中/和/root(~) 和 /home
- NetDMA
- [Math] A love of late toward Mathematics - how to learn it?
- Windows下安装Elasticsearch
- 应用程序加载外部字体文件(使用AddFontResource API函数指定字体)
- MyEclipse 常用设置
- Linux编程环境介绍(1) -- linux的历史
- jsonp与cors跨域的一些理解(转)
- Adapter基本用法
- [.NET] 《Effective C#》读书笔记(二)- .NET 资源托管
- 只需要一点点C++基础,新手也可以制作单机游戏内存修改器
- 如何实现 Service 伸缩?- 每天5分钟玩转 Docker 容器技术(97)
- 项目Alpha冲剂(3/10)
- 简单易用的堡垒机系统—Teleport
- Netty实战 - 1. 基本概念
- nginx:支持跨域访问
- 关于Arch Linux efibootmgr 命令行参数问题
- Android-Thread线程的状态