算法刷题-动态规划2(继续)

算法刷题-动态规划2

  • 珠宝的最高价值
  • 下降路径最小和

珠宝的最高价值

题目
在这里插入图片描述
大佬思路
多开一行使得代码更加的简洁

移动到右侧和下侧
dp[ i ][ j ]有两种情况:
第一种是从上面来的礼物最大价值:dp[ i ][ j ] = dp[ i - 1 ][ j ] + g[ i ][ j ]
第二种是从左面来的礼物最大价值:dp[ i ][ j ] = dp[ i ][ j - 1 ] + g[ i ][ j ]
所以得出状态表达式,dp[ i ][ j ] = max( dp[ i ][ j - 1 ],dp[ i - 1 ][ j ] ) + g[ i ][ j ]
2。为了简洁代码,多增加一行

class Solution {
    public int maxValue(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        //dp[i][j]表示从grid[0][0]到grid[i - 1][j - 1]时的最大价值
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }
}

class Solution { 
public: 
    int maxValue(vector<vector<int>>& grid) { 
        int m = grid.size(), n = grid[0].size(); 
        vector<vector<int>> dp(m + 1, vector<int>(n + 1)); 
        for (int i = 1; i <= m; i++) { 
            for (int j = 1; j <= n; j++) { 
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];

            }
        }
        return  dp[m][n]; 
    }
};

下降路径最小和

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

头文件: #include< algorithm >
返回值: 两个函数返回的都是迭代器,所以要提取数值的话需要在函数前加上*
语法格式: max_element(first,end,cmp);其中cmp为可选择参数(自定义排序可用,默认不需要填)
两个函数默认都是从小到大排列, max_element() 输出最后一个值, min_element() 输出第一个值。
这里要特别注意:如果自定义排序是从大到小的, max_element() 和min_element() 的返回结果相反,也就是说max_element()返回的是最小值,min_element()返回的是最大值 。

  • 定义函数dp[i][j] ,是关于路径到达 i,j 点的最小值
  • 然后找 关系式,分析最后一点是从哪里得到的, 从左上方来:dp[ i - 1 ][ j - 1 ] + m[ i ][ j ],从正上方来:dp[ i - 1 ][ j ] + m[ i ][ j ], 从右上方来:dp[ i - 1 ][ j + 1 ] + m[ i ][ j ]
class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size();
        vector<vector<int>> dp(n, vector<int>(n));
        copy(matrix[0].begin(), matrix[0].end(), dp[0].begin());
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int mn = dp[i - 1][j];
                if (j > 0) {
                    mn = min(mn, dp[i - 1][j - 1]);
                }
                if (j < n - 1) {
                    mn = min(mn, dp[i - 1][j + 1]);
                }
                dp[i][j] = mn + matrix[i][j];
            }
        }
        return *min_element(dp[n - 1].begin(), dp[n - 1].end());
    }
//INT_MAX = 2 ^ 31 - 1,INT_MIN = -2 ^ 31.
//防止越界,在左边,上面和右边都增加一行
//并且将第一行定义为0
class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {

        int m = matrix.size(), n = matrix[0].size();

        vector<vector<int>> dp(m + 1, vector<int>(n + 2, INT_MAX));

        for (auto& e : dp[0]) e = 0;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i - 1][j + 1]))
                    + matrix[i - 1][j - 1];
            }
        }
        int ans = INT_MAX;

        for (const auto& k : dp[m]) ans = min(ans, k);
        return ans;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/181581.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【MySQL】宝塔面板结合内网穿透实现公网远程访问

文章目录 前言1.Mysql服务安装2.创建数据库3.安装cpolar3.2 创建HTTP隧道4.远程连接5.固定TCP地址5.1 保留一个固定的公网TCP端口地址5.2 配置固定公网TCP端口地址 前言 宝塔面板的简易操作性,使得运维难度降低,简化了Linux命令行进行繁琐的配置,下面简单几步,通过宝塔面板cpo…

Course1-Week2-多输入变量的回归问题

Course1-Week2-多输入变量的回归问题 文章目录 Course1-Week2-多输入变量的回归问题1. 向量化和多元线性回归1.1 多维特征1.2 向量化1.3 用于多元线性回归的梯度下降法 2. 使梯度下降法更快收敛的技巧2.1 特征缩放2.2 判断梯度下降是否收敛2.3 如何设置学习率 3. 特征工程3.1 选…

react中的state

没想到hooks中也有state这一说法 看下面的两个案例 1、无state变化不会执行父子函数 2、有state更改执行父子函数

竞赛选题 车道线检测(自动驾驶 机器视觉)

0 前言 无人驾驶技术是机器学习为主的一门前沿领域&#xff0c;在无人驾驶领域中机器学习的各种算法随处可见&#xff0c;今天学长给大家介绍无人驾驶技术中的车道线检测。 1 车道线检测 在无人驾驶领域每一个任务都是相当复杂&#xff0c;看上去无从下手。那么面对这样极其…

数据提取PDF SDK的对比推荐

PDF 已迅速成为跨各种平台共享和分发文档的首选格式&#xff0c;它作为一种数据来源&#xff0c;常见于公司的各种报告和报表中。为了能更好地分析、处理这些数据信息&#xff0c;我们需要检测和提取 PDF 中的数据&#xff0c;并将其转换为可用且有意义的格式。而数据提取的 PD…

【Spring进阶系列丨第四篇】Spring的Bean管理(基于xml的配置)

前言 我们知道&#xff0c;容器是一个空间的概念&#xff0c;一般理解为可盛放物体的地方。在Spring容器通常理解为BeanFactory或者ApplicationContext。我们知道spring的IOC容器能够帮我们创建对象&#xff0c;对象交给spring管理之后我们就不用手动去new对象。 那么Spring是如…

服务号可以迁移到订阅号吗

服务号和订阅号有什么区别&#xff1f;服务号转为订阅号有哪些作用&#xff1f;首先我们要看一下服务号和订阅号的主要区别。1、服务号推送的消息没有折叠&#xff0c;消息出现在聊天列表中&#xff0c;会像收到消息一样有提醒。而订阅号推送的消息是折叠的&#xff0c;“订阅号…

2023“亚太杯”大学生数学建模竞赛

2023亚太杯数学建模C题 中国新能源电动汽车的发展趋势 解题思路、数据 该题并没有提供数据集&#xff0c;对所需数据进行收集整理是对题目进行求解的基础。在本题中&#xff0c;主要需要以下数据&#xff1a;新能源汽车历史销售量、新能汽车相关专利的历史数量、充电桩历史数…

【外贸商机篇】黑色星期五来啦,跨境电商必备手册!

黑色星期五是每年11月的第四个星期五&#xff0c;三天后是网络星期一。这两个购物日是美国一年中最繁忙的购物日之一&#xff0c;仅在2021年的感恩节周末&#xff0c;电子商务收入估计就达到196亿美元。 在一项Statista调查中&#xff0c;美国消费者被问及他们计划购买哪些商品…

太赫兹涂层测厚:为汽车制造商保驾护航

太赫兹涂层测厚&#xff1a;为汽车制造商保驾护航 近年来&#xff0c;专用于测量任何表面涂层厚度的IRYS太赫兹系统&#xff0c;成功赢得了包括大众和丰田在内的全球领先整车厂的信任。 为了实现这一目标&#xff0c;IRYS系统经过了许多制造商为甄选值得信赖的技术供应商而设置…

软件开发及交付中,如何平衡项目进度和团队成员的利益?

在平衡软件质量与时间、成本、范围的关系时&#xff0c;需要考虑到项目管理的金三角概念&#xff0c;即时间、成本和范围。从项目管理的角度来看&#xff0c;项目进度和团队成员的利益需要平衡。 以下是一些建议&#xff1a; 制定可行的计划&#xff1a;让项目相关各方充分参与…

我劝烂了,这东西大学生早用早解脱

大学生看我&#xff0c;这个东西太太太香了啊&#xff01;&#xff01;&#xff01; 要写论文&#xff0c;写总结的都给我用起来 这东西能自动写文章&#xff0c;想写几篇就写几篇&#xff0c;篇篇不重复&#xff01;只要输入一个标题&#xff0c;马上就能生成一篇。真的贼香…

目前软件测试行业发展如何?第三方软件检测机构是否是未来趋势?

随着软件行业的快速发展&#xff0c;软件质量的重要性日益凸显&#xff0c;软件测试也成为了软件开发过程中不可或缺的环节。那么目前软件测试行业的发展如何?第三方软件检测机构又是否是未来软件测试的趋势呢?接下来我们将从多个角度为您详细解答。 目前软件测试行业呈现快…

老师检查家庭作业的作用

在教育体系中&#xff0c;老师检查家庭作业是一种常见的教学方式&#xff0c;旨在帮助学生巩固课堂所学知识&#xff0c;提高自学能力&#xff0c;以及培养良好的学习习惯。家庭作业是学生学习过程中不可或缺的一环&#xff0c;而老师对家庭作业的检查则起到了至关重要的作用。…

内容营销频频出圈,这些品牌号做对了什么?

小红书拥有大量的年轻用户&#xff0c;通过运营品牌号既能降低投放成本&#xff0c;又能更好地连接消费者和品牌&#xff0c;在平台完成一站式闭环营销。 今天就借助几个成功案例&#xff0c;来分析下他们是如何搭建官方账号&#xff0c;通过内容运营吸引更多用户&#xff0c;实…

航天博物馆3D虚拟交互展厅让大众对科技发展有更深切的理解和感受

博物馆作为人们了解历史、文化和艺术的重要场所&#xff0c;现在可以通过VR全景技术来进行展览&#xff0c;让参观者身临其境地感受历史文化的魅力。本文将介绍博物馆VR全景的特点、优势&#xff0c;以及如何使用VR全景技术来使得博物馆的展览和教育活动更丰富。 VR数字博物馆…

Python基础:生成器(Generators)和生成器表达式(Generator Expressions)详解

生成器&#xff08;Generators&#xff09;和 生成器表达式&#xff08;Generator Expressions&#xff09;是 Python 中用于处理迭代器和序列数据的强大工具。它们允许你按需生成值&#xff0c;而不是一次性生成所有值&#xff0c;从而节省内存和提高性能。 1. 生成器&#x…

【完整思路模型代码】2023年第十三届APMCM亚太地区大学生数学建模竞赛C题

2023年第十三届APMCM亚太地区大学生数学建模竞赛C题【完整数据、思路、模型、代码】 C题 中国新能源电动汽车的发展趋势 该题并没有提供数据集&#xff0c;对所需数据进行收集整理是对题目进行求解的基础。在本题中&#xff0c;主要需要以下数据&#xff1a;新能源汽车历史销…

Python入门指南之基本概率和语法基础

文章目录 一、基本概念二、控制流三、函数四、模块五、数据结构六、面向对象的编程七、输入输出八、异常九、Python标准库关于Python技术储备一、Python所有方向的学习路线二、Python基础学习视频三、精品Python学习书籍四、Python工具包项目源码合集①Python工具包②Python实战…

漏洞复现--万户ezoffice FileCheckTemplateEdit SQL注入

免责声明&#xff1a; 文章中涉及的漏洞均已修复&#xff0c;敏感信息均已做打码处理&#xff0c;文章仅做经验分享用途&#xff0c;切勿当真&#xff0c;未授权的攻击属于非法行为&#xff01;文章中敏感信息均已做多层打马处理。传播、利用本文章所提供的信息而造成的任何直…