tqlovepy

用户名：uq_91509931799

访问量：1969

签　名：

编程是爱好，数学是推动爱好前进的好帮手

等　　级
排　　名	2439
经　　验	2307
参赛次数	4
文章发表	3
年　　龄	21
在职情况	学生
学　　校	淮北师范大学
专　　业	光电信息科学与工程

　　自我简介：

爱做题爱python

TA的其他文章

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

八种排序算法（python实现）
浏览：492

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(2) （C++代码）

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

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

优质题解

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

　　作者: tqlovepy　　　　发表时间：2022-01-31 20:19:30 浏览：1181　|　评论：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分

19 人评分

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

　　评论区

fanzetao

咱就是说如果有个数甚至大于所有的数总和代码就崩了

2024-03-12 22:54:43

Sapphire

文章我已经看了，思路上被你点拨了不少，确实是非常好的方法，让我学到了很多东西，但有一点点小问题，我指出一下：
1.int max(int a,int b)
2.dp[i][j] += max(dp[i+1][j],dp[i+1][j+1]);

2022-02-23 20:19:46

tqlovepy

TA的其他文章

你可能喜欢

C语言训练-字符串正反连接（C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C++代码）

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

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

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

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

评论区

精彩推荐

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

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

【回文数(二)】（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C++代码）（手动优化一下计算）

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

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

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

DNA （C语言描述，数据结构）

【金明的预算方案】（C++代码）

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

tqlovepy

TA的其他文章

你可能喜欢

C语言训练-字符串正反连接 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C++代码）

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

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

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

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

评论区

精彩推荐

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

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

【回文数(二)】 （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C++代码）（手动优化一下计算）

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

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

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

DNA （C语言描述，数据结构）

【金明的预算方案】 （C++代码）

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

C语言训练-字符串正反连接（C语言代码）

　　评论区

【回文数(二)】（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C++代码）（手动优化一下计算）

【金明的预算方案】（C++代码）