首页 > 其他分享 >Leetcode(剑指offer专项训练)——DP专项(2)

Leetcode(剑指offer专项训练)——DP专项(2)

时间:2023-03-24 19:44:21浏览次数:60  
标签:专项 triangle int 结点 DP ans 下标 Leetcode dp

三角形中最小路径之和

1.题目描述

给定一个三角形 triangle ,找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标 i ,那么下一步可以移动到下一行的下标 i 或 i + 1 。
链接

2.思路题解

首先想到的最简单的思路是dp存储每个位置对应的最小路径和,每一个位置对应的可能的路径和=min(dp(i-1,j-1),dp(i-1,j)),对于边界条件需要针对性的特别制定,于是题解如下:

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int m=triangle.size();
        if(m==1){
            return triangle[0][0];
        }
        vector<vector<int> >dp(m);
        dp[0]=vector<int>(1);
        dp[0][0]=triangle[0][0];
        int ans=999999;
        for(int i=1;i<m;i++){
            dp[i]=vector<int>(i+1);
            dp[i][0]=dp[i-1][0]+triangle[i][0];
            if(i==m-1&&dp[i][0]<ans){
                ans=dp[i][0];
            }
            for(int j=1;j<i;j++){
                dp[i][j]=min(dp[i-1][j-1],dp[i-1][j])+triangle[i][j];
                if(i==m-1&&ans>dp[i][j]){
                    ans=dp[i][j];
                }
            }
            dp[i][i]=dp[i-1][i-1]+triangle[i][i];
            if(i==m-1&&ans>dp[i][i]){
                ans=dp[i][i];
            }
        }
        return ans;
    }
};

标签:专项,triangle,int,结点,DP,ans,下标,Leetcode,dp
From: https://www.cnblogs.com/SaltyCheese/p/17253145.html

相关文章

  • 编译 pktgen-dpdk
    pktgen是一个linux的高性能发包测试工具,pktgen-dpdk是一个依赖dpdk的高性能发包工具,理论上比pktgen更好一些。pktgenDependency"libdpdk"notfound,triedpkgconfiga......
  • 从DPU角度,谈谈关于国产OS开源社区发展的思考​
    前言   近年来随着国际形势剧变,中国在多个关键技术领域都面临着被“卡脖子”的难题,“国产”这一话题也成为了强技术领域的核心议题之一,操作系统自然不例外。从采购现......
  • LeetCode45. 跳跃游戏 II
    classSolution{public://f[i]表示跳到i所需的最小步数intjump(vector<int>&nums){vector<int>f(10010,0x3f3f3f3f);intn=nums.size()......
  • 用Python编写一个封装mstsc的RDP批量管理工具
    要实现的功能1.调用系统的mstsc命令来实现远程桌面2.确保连接过程不可见,实现直接连接的效果3.支持窗口和全屏连接4.支持手动添加新的桌面5.支持显示桌面列表6.......
  • 【LeetCode动态规划#01】动规入门:求斐波那契数 + 爬楼梯(熟悉解题方法论)
    斐波那契数力扣题目链接(opensnewwindow)斐波那契数,通常用F(n)表示,形成的序列称为斐波那契数列。该数列由0和1开始,后面的每一项数字都是前面两项数字的和。也......
  • CF1168C And Reachability 题解 线性dp
    题目链接https://codeforces.com/problemset/problem/1168/C题目大意给定一个数组\(a\),从下标\(x\)能够转移到下标\(y\)要满足\(x\lty\)且\(a_{p_i}\,\&\,a......
  • 什么时候用ExecutorService,什么时候用ThreadPoolExecutor?
    如果不需要对线程池参数应用任何自定义微调,并且希望使用预配置的线程池实例,则应该选择ExecutorService。ExecutorService提供了几种方法来创建不同类型的线程池,例如固定的......
  • 使用Cursor怒刷LeetCode
    题目:如果一个数列由至少两个元素组成,且每两个连续元素之间的差值都相同,那么这个序列就是 等差数列 。更正式地,数列 s 是等差数列,只需要满足:对于每个有效的 i , s[i+1]......
  • 【leetcode-数组】有效的数独
    判断一个 9x9的数独是否有效。只需要根据以下规则,验证已经填入的数字是否有效即可。数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在......
  • 【leetcode】位1的个数
    编写一个函数,输入是一个无符号整数,返回其二进制表达式中数字位数为‘1’ 的个数(也被称为汉明重量)。 示例1:输入:00000000000000000000000000001011输出:3解释:输入的二进......