首页 > 代码库 > 数字三角形 记忆化搜索与递归
数字三角形 记忆化搜索与递归
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
在上面的数字三角形中寻找在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。
路径上的每一步都只能往左下或右下走。只需要求出这个最大和即可，不必给出具体路径。
三角形的行数大于1小于等于100，数字为 0 - 99
输入格式：
5 //三角形行数。下面是三角形
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
#include <iostream> #include<string.h> #include<stdio.h> #define N 100 using namespace std; int d[N][N],a[N][N]; int t; int solve(int i,int j){ if(d[i][j]>=0) return d[i][j]; return d[i][j]=a[i][j]+(i==t?0:max(solve(i+1,j),solve(i+1,j+1))); } int main(){ memset(d,-1,sizeof(d)); cin>>t; for(int i=1;i<=t;i++) for(int j=1;j<=i;j++) cin>>a[i][j]; cout<<solve(1,1); }
数字三角形 记忆化搜索与递归
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。