HRBUST

用户名：HRBUST123456789

访问量：6648

签　名：

等　　级
排　　名	223
经　　验	6291
参赛次数	0
文章发表	21
年　　龄	0
在职情况	学生
学　　校	哈尔滨理工大学
专　　业

　　自我简介：

TA的其他文章

字符串的反码-题解(C++代码)
浏览：468

链表之报数问题-题解建立循环链表解决
浏览：569

数据结构-图的遍历——DFS深度优先搜索-题解（C++代码）
浏览：180

你可能喜欢

三角形-题解(C++代码)

　　作者: HRBUST　　　　发表时间：2020-02-14 15:09:02 浏览：305　|　评论：0　

原题链接：三角形

此题采用动态规划进行操作
	首先需要考虑该问题的根本要求
	将总问题分割为小问题，题目要求找出最大的数值
	从数塔的最后一层开始寻找，到dp[1][1]结束，倒着寻找最大值，直到到达1，1再停止
	每一步向上寻找可能的路径，分别为i+1，j+1||i+1，两种情况（可以类比搜索进行思考）
	找到两种可能的路径之后用max进行比较，选出大的路径，然后重复以上操作
	本题的思想是递归，但由于时间问题将递归转化为dp方程进行操作，降低时间复杂度（递归会超时）
	
	
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <algorithm>
    #include <cmath>
    #include <iostream>
    using namespace std;
    
    int main()
    {
    	int sum, t, i, j, n, mp[200][200], dp[200][200];
    	cin >> t;
    	while (t--)
    	{
    		cin >> n;
    		for (i = 1; i <= n; i++)
    		{
    			for (j = 1; j <= i; j++)
    			{
    				cin >> mp[i][j];//用来储存地图
    				if (i == n)
    				{
    					dp[i][j] = mp[i][j];//因为从最后一行开始
						//所以将基础数值初始化与mp最后一行相同
    				}
    			}
    		}
    		
    		for (i = n-1; i >= 1; i--)//倒着从n-1开始运算
    		{
    			for (j = 1; j <= i; j++)
    			{
    				dp[i][j] = max(mp[i][j]+dp[i+1][j],mp[i][j]+dp[i+1][j+1]);
    			}
    		}
    		cout << dp[1][1] << endl;
    		dp[101][101] = { 0 };
    	}
    	return 0;
    }

0.0分

1 人评分

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

HRBUST

TA的其他文章

你可能喜欢

字符逆序（C语言代码）

字符串的输入输出处理（C语言代码）

川哥的吩咐（C语言代码）

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

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

三角形-题解(C++代码)

评论区

精彩推荐

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

1113题解

矩阵乘方（C语言代码）

Tom数（C语言代码）

陶陶摘苹果2 （C语言代码）

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

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

最好的，

【偶数求和】（C语言代码）

1273题解

HRBUST

TA的其他文章

你可能喜欢

字符逆序 （C语言代码）

字符串的输入输出处理 （C语言代码）

川哥的吩咐 （C语言代码）

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

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

三角形-题解(C++代码)

评论区

精彩推荐

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

1113题解

矩阵乘方 （C语言代码）

Tom数 （C语言代码）

陶陶摘苹果2 （C语言代码）

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

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

最好的，

【偶数求和】 （C语言代码）

1273题解

字符逆序（C语言代码）

字符串的输入输出处理（C语言代码）

川哥的吩咐（C语言代码）

　　评论区

矩阵乘方（C语言代码）

Tom数（C语言代码）

【偶数求和】（C语言代码）