猿创征文 |【算法面试入门必刷】动态规划-线性dp（二）

📦个人主页：一二三o-0-O的博客
🏆技术方向：C/C++客户端资深工程师（直播+音视频剪辑）
👨‍💻作者简介：数据结构算法与音视频领域创作者
📒 系列专栏：牛客网面试必刷
📣专栏目标：帮助伙伴们通过系统训练，掌握数据结构与算法，收获心仪Offer
📝推荐一个找工作神器：牛客刷题网 【面试经验|实习招聘内推，求职就业一战解决】
🧡如果对您有帮助的话，欢迎点赞👍收藏📂，关注不迷路

【算法入门必刷】数据结构-栈篇系列文章：
【算法入门必刷】数据结构-栈（一）
【算法入门必刷】数据结构-栈（二）
【算法入门必刷】数据结构-栈（三）
【算法入门必刷】数据结构-栈（四）
【算法入门必刷】数据结构-栈（五）

【算法入门必刷】动态规划-线性dp篇系列文章：
【算法面试入门必刷】动态规划-线性dp（一）
【算法面试入门必刷】动态规划-线性dp（二）
【算法面试入门必刷】动态规划-线性dp（三）

前言

开启刷题，请点击右边链接进行跳转点击这里

算法入门刷题训练

题目AB35：三角形最小路径和

题目分析

给定一个正三角形数组，自顶到底分别有 1，2，3，4，5…，n 个元素，找出自顶向下的最小路径和。
每一步只能移动到下一行的相邻节点上，相邻节点指下行种下标与之相同或下标加一的两个节点。
数据范围：三角形数组行数满足1≤n≤200 ，数组中的值都满足∣val∣≤10^4

如果已经看过【算法面试入门必刷】动态规划-线性dp（一）的伙伴，看到这道三角形最小路径题目，可以推理出最底层的某一个节点和等于上一层同列节点的和与上一层前一列节点的和的最小值加上当前值。如下图所示：即sumC = min(sumA,sumB) + 1。经过这样的分析可以得出递推公式：f(i)(j) = min(f(i-1)(j),f(i-1)(j-1)) + num（i表示当前行数，j表示当前列数）；

理论准备

任何算法都有相对应的算法模板或者有规律的解题步骤。对于动态规划来讲，做DP相关的算法题要熟练掌握下面DP解题步骤，这样有助于在面对到各种各样的题目时能够提高解题效率：

DP解题步骤:

1. 首先要确定dp数组：是一维，二维还是三维；以及下标的含义是什么？
2. 根据确定好的dp数组，给出递推公式，也叫状态转移方程。
3. 确定dp数组是否需要初始化，初始化为多少。
4. 确定遍历的顺序；这一步在背包相关的DP题目中非常重要。
5. 根据测试用例进行验证

题解

具体的解决方案如下：

1. 首先确定dp数组：是一维，二维还是三维；以及下标的含义是什么？

// 这里使用二维dp，因为有行列
// dp[i][j] 表示到达第i行第j列的节点自顶向下的最小路径和为dp[i][j]
vector<vector<int>> dp(300,vector<int>(300));
1
2
3

2. 根据确定好的dp数组，给出递推公式。

// 根据题目分析我们得出了以下递推公式
if(j == 0){// 处理左侧的边界条件
    dp[i][j] = dp[i-1][j] + triangle[i][j];
}else if(j == n-1){// 处理右侧的边界条件
    dp[i][j] = dp[i-1][j-1] + triangle[i][j];
}else{// 正常节点
    dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]) + triangle[i][j];
}
1
2
3
4
5
6
7
8

3. 确定dp数组是否需要初始化，初始化为多少。

// 根据本题的边界条件，只需要将dp[0][0]赋值为三角形的顶点即可
dp[0][0] = triangle[0][0];
1
2

4. 确定遍历的顺序；这一步在背包相关的DP题目中非常重要。

// 本题从小到大遍历行，从小到大遍历列
for(int i{1};i < m;++i){
	vector<int> colV = triangle[i];
	int n = colV.size();

	for(int j{};j<n;++j){
	}
}
1
2
3
4
5
6
7
8

5. 根据测试用例进行验证：选择所有的测试用例带入验证即可。

6. 完整代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param triangle int整型vector> 
     * @return int整型
     */
    int minTrace(vector<vector<int> >& triangle) {
        // write code here
        
        vector<vector<int>> dp(300,vector<int>(300));
        int m = triangle.size();
        
        dp[0][0] = triangle[0][0];
        int result{dp[0][0]};
        
        for(int i{1};i < m;++i){
            vector<int> colV = triangle[i];
            int n = colV.size();
            
            int minValue{INT_MAX};
            for(int j{};j<n;++j){
                if(j == 0){
                    dp[i][j] = dp[i-1][j] + triangle[i][j];
                }else if(j == n-1){
                    dp[i][j] = dp[i-1][j-1] + triangle[i][j];
                }else{
                    dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]) + triangle[i][j];
                }
                
                
                if(i == m-1) {
                    if(dp[i][j] < minValue) minValue = dp[i][j];
                }
            }
            
            result = minValue;
        }
        
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

当提交成功后，会展示如下界面，那么恭喜这道题目就通过了！

小结

祝愿所有的伙伴都能拿到自己心仪的Offer！📣伙伴们点击右边链接立刻开启刷题吧：牛客——刷题网