Lomid1024

#1177: 三角形,C++动态规划实现
####题目描述：
[题目 1177: 三角形](https://www.dotcpp.com/oj/problem1177.html "题目 1177: 三角形")
####解题思路：
****其实这道题很简单，只需要用深度优先搜索算法或广度优先搜索算法就可以实现题目的要求。但深度优先算法对于这一题有个致命缺点，就是他会大量地重复计算已经计算过的点，十分浪费时间，效率极其低下。想要解决这个缺点其实很简单，就是标记已经计算过的点，第二次就不需重复计算。说着好像很复杂，但代码实现其实还是很简单的。如果看不懂以上思路，可以直接参考以下代码****
####代码实现：
```cpp
//当前结果=上一步结果+下一层max(向左下的值，向右下的值)，所以最后结果存放在[1][1]
//f[x][y]=a[x][y]+max(dfs(x+1,y),dfs(x+1,y+1))
#include<bits/stdc++.h>
using namespace std;
int a[50][50],f[50][50],n,t; //f用于储存结果
int dfs(int x,int y)
{
	if(f[x][y]==-1)
	{
		if(x==n) f[x][y]=a[x][y];
		else f[x][y]=a[x][y]+max(dfs(x+1,y),dfs(x+1,y+1));//比较左下和右下的大小
	}
	return f[x][y];
}
int main()
{
	cin>>t;
	for(int i=1;i<=t;i++){
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=i;j++)
			{
				cin>>a[i][j];
				f[i][j]=-1;    //初始化为-1
			}
		}
		dfs(1,1);
		cout<<f[1][1]<<endl;   //输出最终结果
	}
	return 0;
}
```
####代码总结：
****以上代码为“动态规划”的思路，如果想要深入了解动态规划，可到互联网上搜寻相关文章，这里就不在解释****

声明：本人也是动态规划的初学者，可能有许多说错的地方（我自己也怀疑我的代码是否真的用了动态规划），请多多指教！谢谢！

0.0分

0 人评分

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

Lomid1024

TA的其他文章

你可能喜欢

简单的a+b （C语言代码）

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

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

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

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

1177: 三角形,C++动态规划实现

评论区

精彩推荐

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

不知道哪里错了

Biggest Number （C++代码）回溯法

矩形面积交（Java代码）

买不到的数目（C++代码）

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

WU-拆分位数（C++代码）

用筛法求之N内的素数。（C语言代码）

DNA （C语言代码）

水仙花（C语言代码）

Lomid1024

TA的其他文章

你可能喜欢

简单的a+b （C语言代码）

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

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

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

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

1177: 三角形,C++动态规划实现

评论区

精彩推荐

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

不知道哪里错了

Biggest Number （C++代码）回溯法

矩形面积交 （Java代码）

买不到的数目 （C++代码）

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

WU-拆分位数 （C++代码）

用筛法求之N内的素数。 （C语言代码）

DNA （C语言代码）

水仙花 （C语言代码）

　　评论区

矩形面积交（Java代码）

买不到的数目（C++代码）

WU-拆分位数（C++代码）

用筛法求之N内的素数。（C语言代码）

水仙花（C语言代码）