动态规划经典例题leetcode思路代码详解

目录

动态规划基础篇例题

leetcode70题.爬楼梯

leetcode746题.使用最小花费爬楼梯

leetcode198题.打家劫舍

leetcode62题.不同路径

leetcode64题.最小路径和

leetcode63题.63不同路径II

动态规划基础篇例题

这一篇的例题解答是严格按照我上一篇写的动态规划三部曲做的，对动态规划不太了解或者比较感兴趣的朋友可以看我上一篇文章。

动态规划算法详解基础篇-CSDN博客

leetcode70题.爬楼梯

70. 爬楼梯 - 力扣（LeetCode）

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提示：

  • 1 <= n <= 45
class Solution {
    /*动态规划三部曲
        第一步：
        dp[i]数组含义：表示爬到第i个台阶时，一共有dp[i]种爬法。

        第二步：求关系时
        dp[i] dp[i-1] dp[i-2]
        要么是从i-1跳上来 要么就是从i-2跳上来的 
        dp[i] = dp[i-1] + dp[i-2];

        第三步：初始值
        dp[0] = 1;
        dp[1] = 1
        dp[2] = 2;

    */
    public int climbStairs(int n) {

        if(n <= 1){
            return 1;
        }

        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }

        return dp[n];
    }
}

leetcode746题.使用最小花费爬楼梯

746. 使用最小花费爬楼梯 - 力扣（LeetCode）

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

示例 1：

输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。

示例 2：

输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。

提示：

  • 2 <= cost.length <= 1000
  • 0 <= cost[i] <= 999
class Solution {
    /*
        动态规划三部曲：
        1、dp[i]：我们爬到第 i 层是，需要花费 dp[i] 元。

        2、求关系式
          要跳到 i 层，
        （1）要么从第 i-1 跳上来 dp[i] = dp[i-1] + cost[i]
         (2)要么从第 i-2 跳上来 dp[i] = dp[i-2] + cost[i]。
         dp[i] = min(dp[i-1], dp[i-2]) + cost
            for(i = 2)
         3、初始值
            dp[0] = cost[0]
            dp[1] = cost[1]


    */
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n];
        dp[0] = cost[0];
        dp[1] = cost[1];

        for(int i = 2; i < n; i++){
            dp[i] = Math.min(dp[i-1], dp[i-2]) + cost[i];
        }

        return Math.min(dp[n-1], dp[n-2]);
    }
}

leetcode198题.打家劫舍

198. 打家劫舍 - 力扣（LeetCode）

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 400
/*
 1、dp[i]:到达第i个房间时偷到的最高金额是dp[i]
 2、dp[i] = nums[i] + dp[i - 2] 偷当前屋子
    dp[i] = dp[i - 1]  不偷当前屋子
    选一个比较大的

 3、dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])

*/
class Solution {
    public int rob(int[] nums) {
        if(nums.length <= 1){
            return nums[0];
        }
        if(nums.length <= 2){
            return Math.max(nums[0], nums[1]);
        }
        int[] dp = new int[nums.length];

        // 初始值
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        // dp[i] = max(nums[i] + dp[i-2], dp[i-1]);
        for(int i = 2; i < nums.length; i++){
            dp[i] = Math.max(nums[i] + dp[i-2], dp[i-1]);
        }

        return dp[nums.length-1];

    }
}

leetcode62题.不同路径

62. 不同路径 - 力扣（LeetCode）

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

img

输入：m = 3, n = 7
输出：28

示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

输入：m = 7, n = 3
输出：28

示例 4：

输入：m = 3, n = 3
输出：6

提示：

  • 1 <= m, n <= 100
  • 题目数据保证答案小于等于 2 * 109
/*

1、定义：dp[i][j]:到达[i, j]时，一共有dp[i, j]个路径
2、关系式：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
3、初始化
   dp[0][0...m - 1] = 1
   dp[0...n - 1][0] = 1

*/

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];

        // 初始值
        //最左边的一列
        for(int i = 0; i < m; i++){
            dp[i][0] = 1;
        }
        //最上边的一行
        for(int i = 0; i < n; i++){
            dp[0][i] = 1;
        }

        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }

        return dp[m-1][n-1];

    }
}

leetcode64题.最小路径和

64. 最小路径和 - 力扣（LeetCode）

给定一个包含非负整数的 *m* x *n* 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例 1：

img

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 200
class Solution {
    /*动态规划三部曲

    1、定义数组含义
    dp[i][j]:当到达 (i,j) 这个位置时，最小路径和为 dp[i][j]。

    2、关系式
    dp[i][j]. dp[i-1][j] dp[i][j-1]
    如何才能到达 （i，j）
    （1）要么从 （i-1,j) 这个位置向下走一步=>dp[i][j] = dp[i-1][j] + grid[i][j]
    （2）要么是从(i,j-1)这个位置向右走一步=>dp[i][j] = dp[i][j-1] + grid[i][j]

    dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

    3、初始值
    dp[0][0~m-1]
    dp[0~n-1][0]

    */
    public int minPathSum(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int[][] dp = new int[n][m];
        // 求初始值
        dp[0][0] = grid[0][0];
        for(int j = 1; j < m; j++){
            dp[0][j] = dp[0][j-1] + grid[0][j];
        }
        for(int i = 1; i < n; i++){
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }

        for(int i = 1; i < n; i++){
            for(int j = 1; j < m; j++){
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
            }
        }
        return dp[n-1][m-1];
    }
}

leetcode63题.63不同路径II

63. 不同路径 II - 力扣（LeetCode）

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1：

img

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

示例 2：

img

输入：obstacleGrid = [[0,1],[0,0]]
输出：1

提示：

  • m == obstacleGrid.length
  • n == obstacleGrid[i].length
  • 1 <= m, n <= 100
  • obstacleGrid[i][j] 为 0 或 1
class Solution {
    /*
        第一步：
        dp[i][j]:表示走到（i，j）这个地方一共有 dp[i][j]条路径
        第二步：找关系式
        if(obstacleGrid[i][j] == 1){
            dp[i][j] = 0
        }else{
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
        }

        第三步：初始值
        dp[0][0] = obstacleGrid[0][0] == 1? 0 : 1; 
        dp[0][j] = dp[0][j-1]
        dp[i][0] = dp[i-1][0];


    */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid.length;
        int m = obstacleGrid[0].length;
        int[][] dp = new int[n][m];

        dp[0][0] = obstacleGrid[0][0] == 1 ? 0 : 1;
        // 最上面一行
        for(int j = 1; j < m; j++){
            dp[0][j] = obstacleGrid[0][j] == 1 ? 0 : dp[0][j-1];
        }
        // 最左边一列
        for(int i = 1; i < n; i++){
            dp[i][0] = obstacleGrid[i][0] == 1 ? 0 : dp[i-1][0];
        }

        for(int i = 1; i < n; i++){
            for(int j = 1; j < m; j++){
                if(obstacleGrid[i][j] == 1){
                    dp[i][j] = 0;
                }else{
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        return dp[n-1][m-1];

    }
}

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

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

相关文章

【机器学习】算法性能评估常用指标总结

【机器学习】算法性能评估常用指标总结

考虑一个二分问题&#xff0c;即将实例分成正类&#xff08;positive&#xff09;或负类&#xff08;negative&#xff09;。对一个二分问题来说&#xff0c;会出现四种情况。如果一个实例是正类并且也被 预测成正类&#xff0c;即为真正类&#xff08;True positive&#xff0…
阅读更多...
【图解系列】一张图带你了解 DevOps 生态工具

【图解系列】一张图带你了解 DevOps 生态工具

一张图带你了解 DevOps 生态工具 ✅ 协作&#xff08;Collaborate&#xff09;&#xff1a;JIRA、Confluence 大家肯定不陌生了&#xff0c;我之前也写过利用 Jekyll 搭建个人博客的帖子。✅ 构建&#xff08;Build&#xff09;&#xff1a;常用的 SCM&#xff08;Software Con…
阅读更多...
【数据结构】时间和空间复杂度

【数据结构】时间和空间复杂度

马上就要进入到数据结构的学习了 &#xff0c;我们先来了解一下时间和空间复杂度&#xff0c;这也可以判断我们的算法是否好坏&#xff1b; 如何衡量一个算法的好坏&#xff1f; 就是看它的算法效率 算法效率 算法效率分析分为两种&#xff1a;第一种是时间效率&#xff0c;第…
阅读更多...
Android自动化测试必备的测试框架

Android自动化测试必备的测试框架

Appium Appium是一个开源的移动测试工具&#xff0c;支持iOS和Android&#xff0c;它可以用来测试任何类型的移动应用&#xff08;原生、网络和混合&#xff09;。作为一个跨平台的工具&#xff0c;你可以在不同的平台上运行相同的测试。为了实现跨平台的功能&#xff0c;Appiu…
阅读更多...
AI创作工具：Claude2注册保姆级教程

AI创作工具：Claude2注册保姆级教程

最近软件打算多接入几个AI写作平台&#xff0c;包括讯飞星火&#xff0c;百度文心&#xff0c;Claude2&#xff0c;这样就能给用户提供更多的写作选择 经过半天的调研&#xff0c;讯飞星火&#xff0c;百度文心一言&#xff0c;接入都比较简单&#xff0c;毕竟是国内的。 在调…
阅读更多...
【后端卷前端】

【后端卷前端】

为啥现在对后端要求这么高?为啥不要求前端会后端呢? 可能是后端人太多了,要求后端需要会前端的框架(vue react angular ), 这不我为了适应市场的需求来系统的学习vue了: 生成一个基础的vue项目 创建vue项目 vue create projectname 创建vitevue npm init vitelatest p…
阅读更多...
Kafka系列 - 生产者客户端架构以及3个重要参数

Kafka系列 - 生产者客户端架构以及3个重要参数

整体架构 整个生产者客户端由两个县城协调运行&#xff0c;这两个线程分别为主线程和Sender线程&#xff08;发送线程&#xff09;。 主线程中由KafkaProducer创建消息&#xff0c;然后通过可能的拦截器&#xff0c;序列化器和分区器之后缓存到消息累加器&#xff08;RecordAc…
阅读更多...
面试cast：reinterpret_cast/const_cast/static_cast/dynamic_cast

面试cast：reinterpret_cast/const_cast/static_cast/dynamic_cast

目录 1. cast 2. reinterpret_cast 3. const_cast 3.1 加上const的情况 3.2 去掉const的情况 4. static_cast 4.1 基本类型之间的转换 4.2 void指针转换为任意基本类型的指针 4.3 子类和父类之间的转换 5. dynamic_cast 5.1 RTTI(Run-time Type Identification) 1.…
阅读更多...
kafka 集群 KRaft 模式搭建

kafka 集群 KRaft 模式搭建

Apache Kafka是一个开源分布式事件流平台&#xff0c;被数千家公司用于高性能数据管道、流分析、数据集成和关键任务应用程序 Kafka 官网&#xff1a;https://kafka.apache.org/ Kafka 在2.8版本之后&#xff0c;移除了对Zookeeper的依赖&#xff0c;将依赖于ZooKeeper的控制器…
阅读更多...
【JavaEE初阶】线程安全问题及解决方法

【JavaEE初阶】线程安全问题及解决方法

目录 一、多线程带来的风险-线程安全 1、观察线程不安全 2、线程安全的概念 3、线程不安全的原因 4、解决之前的线程不安全问题 5、synchronized 关键字 - 监视器锁 monitor lock 5.1 synchronized 的特性 5.2 synchronized 使用示例 5.3 Java 标准库中的线程安全类…
阅读更多...
vscode运行c++程序如何支持c++11

vscode运行c++程序如何支持c++11

参考https://zhuanlan.zhihu.com/p/269244754 更改setting.json文件
阅读更多...
Spring cloud - Feign

Spring cloud - Feign

Feign的作用 Feign是Netflix公司开发的声明式web客户端组件&#xff0c;Spring对Feign做了无缝集成&#xff1a; Feign is a declarative web service client. It makes writing web service clients easier. To use Feign create an interface and annotate it. It has plugg…
阅读更多...
什么是 Jest ? Vue2 如何使用 Jest 进行单元测试？Vue2 使用 Jest 开发单元测试实例

什么是 Jest ? Vue2 如何使用 Jest 进行单元测试？Vue2 使用 Jest 开发单元测试实例

什么是Jest? Jest 是一个流行的 JavaScript 测试框架，由 Facebook 开发并维护，专注于简单性和速度。它通常用于编写 JavaScript 和 TypeScript 应用程序的单元测试、集成测试和端到端测试。 特点： 简单易用： Jest 提供简洁的 API 和易于理解的语法，使得编写测试用例变得…
阅读更多...
kolla-ansible 部署OpenStack云计算平台

kolla-ansible 部署OpenStack云计算平台

目录 一、环境 二、安装及部署 三、测试 一、环境 官方文档&#xff1a;https://docs.openstack.org/kolla-ansible/yoga/user/quickstart.html rhel8.6 网络设置&#xff1a; 修改网卡名称 网络IP&#xff1a; 主机名&#xff1a; 网络时间协议 配置软件仓库 vim docke…
阅读更多...
模拟退火算法应用——求解二元函数的最小值（极小值）

模拟退火算法应用——求解二元函数的最小值（极小值）

仅作自己学习使用 一、问题 二、代码 clear clcT1 cputime; xmax 5; xmin -5; ymax 5; ymin -5; L 20; % 马尔科夫链长度 dt 0.998; % 降温系数 S 0.02; % 步长因子 T 200; % 初始温度 TZ 1e-8; % 容差 Tmin 0.01;% 最低温度 P 0; % Metropolis接受…
阅读更多...
持续集成交付CICD：GitLabCI 通过trigger触发流水线

持续集成交付CICD：GitLabCI 通过trigger触发流水线

目录 一、理论 1.GitLabCI 二、实验 1.搭建共享库项目 2.GitLabCI 通过trigger触发流水线 三、问题 1.项目app02未触发项目app01 2.GitLab 报502网关错误 一、理论 1.GitLabCI (1) 概念 GitLab CI&#xff08;Continuous Integration&#xff09;是一种持续集成工具…
阅读更多...
为什么要隐藏id地址？使用IP代理技术可以实现吗？

为什么要隐藏id地址？使用IP代理技术可以实现吗？

随着网络技术的不断发展&#xff0c;越来越多的人开始意识到保护个人隐私的重要性。其中&#xff0c;隐藏自己的IP地址已经成为了一种常见的保护措施。那么&#xff0c;为什么要隐藏IP地址&#xff1f;使用IP代理技术可以实现吗&#xff1f;下面就一起来探讨这些问题。 首先&am…
阅读更多...
蓝桥杯每日一题2023.11.24

蓝桥杯每日一题2023.11.24

题目描述 #include <stdio.h> #define N 100int connected(int* m, int p, int q) {return m[p]m[q]? 1 : 0; }void link(int* m, int p, int q) {int i;if(connected(m,p,q)) return;int pID m[p];int qID m[q];for(i0; i<N; i) ________________________________…
阅读更多...
没搞懂二维差分是什么怎么办？？？

没搞懂二维差分是什么怎么办？？？

摸鱼的时候画的&#xff0c;根据公式反推 一维差分倒是懂了 a[10]{1,2,6,9,11,12,17,21,32,67}; c[10]{1,1,4,3,2,1,5,4,11,35}; 现要把[3,7]的值都增加3 c[10]{1,1,7,3,2,1,5,1,11,35}; 要查询的时候再用for循环相加 结论&#xff1a;成立且适用于多次修改 不知道为什么这个…
阅读更多...
跨域攻击分析和防御（上）

跨域攻击分析和防御（上）

点击星标&#xff0c;即时接收最新推文 跨域攻击 在大型公司或大型跨国企业中都拥有自己的内网&#xff0c;跨国公司都有各个子公司一般以建立域林进行共享资源。根据不同职能区分的部门&#xff0c;从逻辑上以主域和子域进行划分以方便统一管理。在物理层使用防火墙将各个子公…
阅读更多...
最新文章

Copyright @ 2022~2023