dp保姆级题解（python+ c语言+ c++三种语言实现 + 代码图解）

1284 阅读 4 评论 2 点赞

原题链接：三角形

**题目**：

7
3 8 
8 1 0
2 7 4 4
4 5 2 6 5

问从上到下走一条路径，路径的数字最大和是多少？每步只能走正下或者右下
题目叙述是左下，但应是逻辑上的正下。

、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、

**本题是典型的dp（动态规划）入门题目**

dp三步走：

①**定义dp方程的含义**
定义是dp的重点，但也有迹可循，一般是定义二阶的dp【i】【j】
此题dp方程的含义可以定义为走到第i行第j列时的最大和是多少

②**找出dp方程（或称状态转移方程）**
也就是找出递推式，我们先手写模拟解题的过程：
题目是说从上往下，但这样不好分析，因为从上往下分析，最下面有n个出口。
所以我们从下往上分析可以很明显的知道更新完整个矩阵之后，答案就是dp[0][0]
从题目倒数第二行开始，想一下2怎么更新？，是不是从它正下和右下选出最大数再加上他本身，所以2更新为 2 + 5 = 7.
那7怎么更新呢，是不是从它正下的5和右下的2选出最大数是5再加上它本身的7得到12
选最大值这个动作怎么用代码表示？可以抽象为max（正下的数，右下的数）
所以手推模拟后发现dp方程是dp[i][j] = max( dp [i+1] [j] , dp [i+1] [j+1]) (0 <= i <= n -1,0 <= j <= i)(i表示行，j表示列，都是从0开始)
有很多人发现了我们没有从最后一行开始往上推，而是从倒数第二行往上推的
这就涉及到我们下面要讲的初始边界确定

③**确定初始边界状态**
因为最后一行下面没有路了，所以最后一行的值不用更新就是他们本身，
则初始状态就是当i = n - 1时，a[i][j] = 他们本身(i表示行，j表示列，都是从0开始)

、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、

三步走完成之后我们就可以开始着手写代码，三种语言代码如下：

**python**
```python
T = int(input())
for i in range(T):
	n = int(input())
	dp = []
	#定义一个二维列表
	for i in range(n):
		#输入路径上的数据
		t = list(map(int,input().split()))
		dp.append(t)
	for i in range(n-2,-1,-1):
		#n-2表示从第二行开始往上推
		for j in range(i+1):
			#列坐标不得超过当前的行坐标
			dp[i][j] += max(dp[i+1][j],dp[i+1][j+1])
			#当前的值等于正下(dp[i+1][j])和右下(dp[i+1][j+1])的最大数加上他本身
	print(dp[0][0])
	#输出结果

```
**c++**
```cpp
#include<iostream>
#include<algorithm>
using namespace std;
int dp[110][110];
int main(){
	int T,n;
	cin >> T;
	while(T--){
		cin >> n;
		//输入部分
		for(int i = 0;i < n;i++)
			for(int j = 0;j <= i;j++)
				cin >> dp[i][j];
		//输入部分
		for(int i = n - 2;i >= 0;i--)
			//从倒数第二行开始往第一行更新值
			for(int j = 0;j <= i;j++)
				//当前行值不得超过列值
				dp[i][j] += max(dp[i+1][j],dp[i+1][j+1]);
				//当前的值等于正下(dp[i+1][j])和右下(dp[i+1][j+1])的最大数加上他本身
		cout << dp[0][0] << endl;
		//输出结果
	}
	return 0;
}
```

**c语言**
```c
#include<stdio.h>
int dp[110][110];
int max(a,b){       //定义在主函数之前不用声明
	if a >= b:
		return a;
	else 
		return b;
}
int main{
	int T,n,i,j;
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		//输入部分
		for(i = 0;i < n;i++)
			for(j = 0;j <= i;j++)
				scanf("%d",&dp[i][j]);
		//输入部分
		for(i = n - 2;i >= 0;--i)
			//从倒数第二行开始往第一行更新值
			for(j = 0;j <= i;j++)
				//当前行值不得超过列值
				dp[i][j] += max(dp[i+1][j],dp[i+1][j+1]);
			//当前的值等于正下(dp[i+1][j])和右下(dp[i+1][j+1])的最大数加上他本身
		printf("%d",dp[0][0]);
		//输出结果
	}
	return 0;
}
```

0.0分

18 人评分

本文分类：题解列表
浏览次数：1284 次浏览
发布日期：2022-01-31 20:19:30
本文链接：https://blog.dotcpp.com/a/83370

上一篇 > 数组输出 (Java代码）
下一篇 > 1434: 蓝桥杯历届试题-回文数字

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

dp保姆级题解（python+ c语言+ c++三种语言实现 + 代码图解）

评论列表共有 4 条评论

发表评论取消回复

dp保姆级题解（python+ c语言+ c++三种语言实现 + 代码图解）

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 4 条评论

发表评论 取消回复

评论列表共有 4 条评论

发表评论取消回复