java算法day45 | 动态规划part07 ● 70. 爬楼梯 (进阶) ● 322. 零钱兑换 ● 279.完全平方数

70. 爬楼梯 (进阶)

题目描述:
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。
输入描述:输入共一行,包含两个正整数,分别表示n, m
输出描述:输出一个整数,表示爬到楼顶的方法数。
输入示例:3 2
输出示例:3
提示:
当 m = 2,n = 3 时,n = 3 这表示一共有三个台阶,m = 2 代表你每次可以爬一个台阶或者两个台阶。
此时你有三种方法可以爬到楼顶。
1 阶 + 1 阶 + 1 阶段
1 阶 + 2 阶
2 阶 + 1 阶

  1. 确定dp数组以及下标的含义
    dp[i]:爬到有i个台阶的楼顶,有dp[i]种方法。

  2. 确定递推公式
    在动态规划:494.目标和 (opens new window)、 动态规划:518.零钱兑换II (opens new window)、动态规划:377. 组合总和 Ⅳ (opens new window)中我们都讲过了,求装满背包有几种方法,递推公式一般都是dp[i] += dp[i - nums[j]];
    本题呢,dp[i]有几种来源,dp[i - 1],dp[i - 2],dp[i - 3] 等等,即:dp[i - j]
    那么递推公式为:dp[i] += dp[i - j]

  3. dp数组如何初始化
    既然递归公式是 dp[i] += dp[i - j],那么dp[0] 一定为1,dp[0]是递归中一切数值的基础所在,如果dp[0]是0的话,其他数值都是0了。
    下标非0的dp[i]初始化为0,因为dp[i]是靠dp[i-j]累计上来的,dp[i]本身为0这样才不会影响结果

  4. 确定遍历顺序
    这是背包里求排列问题,即:1、2 步 和 2、1 步都是上三个台阶,但是这两种方法不一样!
    所以需将target放在外循环,将nums放在内循环。
    每一步可以走多次,这是完全背包,内循环需要从前向后遍历。

  5. 举例来推导dp数组

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int m=in.nextInt();
        int[] dp=new int[n+1];
        dp[0]=1;
        for(int j=1;j<=n;j++){
            for(int i=0;i<=m;i++){
                if(j>=i){
                    dp[j]=dp[j]+dp[j-i];
                }
            }
        }
        System.out.println(dp[n]);
    }
}

时间复杂度:O(mn)
空间复杂度:O(n)

322. 零钱兑换

在这里插入图片描述
在这里插入图片描述
动规五部曲分析如下:

  1. 确定dp数组以及下标的含义
    dp[j]:凑足总额为j所需钱币的最少个数为dp[j]

  2. 确定递推公式
    凑足总额为j - coins[i]的最少个数为dp[j - coins[i]],那么只需要加上一个钱币coins[i]即dp[j - coins[i]] + 1就是dp[j](考虑coins[i])
    所以dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的。
    递推公式:dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

  3. dp数组如何初始化
    首先凑足总金额为0所需钱币的个数一定是0,那么dp[0] = 0;
    其他下标对应的数值呢?
    考虑到递推公式的特性,dp[j]必须初始化为一个最大的数,否则就会在min(dp[j - coins[i]] + 1, dp[j])比较的过程中被初始值覆盖。
    所以下标非0的元素都是应该是最大值。

  4. 确定遍历顺序
    本题求钱币最小个数,那么钱币有顺序和没有顺序都可以,都不影响钱币的最小个数。
    所以本题并不强调集合是组合还是排列。
    综上所述,遍历顺序为:coins(物品)放在外循环,target(背包)在内循环。且内循环正序。

  5. 举例推导dp数组

class Solution {
    public int coinChange(int[] coins, int amount) {
        int max=Integer.MAX_VALUE;
        int[] dp=new int[amount+1];
        for(int i=0;i<dp.length;i++){
            dp[i]=max;
        }
        dp[0]=0;
        for(int i=0;i<coins.length;i++){
            for(int j=coins[i];j<=amount;j++){
                if(dp[j-coins[i]]!=max){//只有dp[j-coins[i]]不是初始最大值时,该位才有选择的必要
                dp[j]=Math.min(dp[j],dp[j-coins[i]]+1);
                }
            }
        }
        return dp[amount]==max?-1:dp[amount];
    }
}

时间复杂度: O(n * amount),其中 n 为 coins 的长度
空间复杂度: O(amount)

279.完全平方数

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

动规五部曲分析如下:

  1. 确定dp数组(dp table)以及下标的含义
    dp[j]:和为j的完全平方数的最少数量为dp[j]

  2. 确定递推公式
    dp[j] 可以由dp[j - i * i]推出, dp[j - i * i] + 1 便可以凑成dp[j]。
    此时我们要选择最小的dp[j],所以递推公式:dp[j] = min(dp[j - i * i] + 1, dp[j]);

  3. dp数组如何初始化
    dp[0]表示 和为0的完全平方数的最小数量,那么dp[0]一定是0。
    有同学问题,那0 * 0 也算是一种啊,为啥dp[0] 就是 0呢?
    看题目描述,找到若干个完全平方数(比如 1, 4, 9, 16, …),题目描述中可没说要从0开始,dp[0]=0完全是为了递推公式。
    非0下标的dp[j]应该是多少呢?
    从递归公式dp[j] = min(dp[j - i * i] + 1, dp[j]);中可以看出每次dp[j]都要选最小的,所以非0下标的dp[j]一定要初始为最大值,这样dp[j]在递推的时候才不会被初始值覆盖。

  4. 确定遍历顺序
    我们知道这是完全背包,
    如果求组合数就是外层for循环遍历物品,内层for遍历背包。
    如果求排列数就是外层for遍历背包,内层for循环遍历物品。

class Solution {
    public int numSquares(int n) {
        int max = Integer.MAX_VALUE;
        int[] dp = new int[n + 1];
        for (int j = 0; j <= n; j++) {//初始化
            dp[j] = max;
        }
        dp[0]=0;
        for(int i=1;i*i<=n;i++){
            int weight=i*i;
            for(int j=weight;j<=n;j++){
                dp[j]=Math.min(dp[j],dp[j-weight]+1);
            }
        }
        return dp[n];
    }
}

时间复杂度: O(n * √n)
空间复杂度: O(n)

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

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

相关文章

【JavaSE】注解

概念解释 注解与注释 注释&#xff1a;用文字描述程序的,是给程序员看的。 注解&#xff1a;用来解释说明程序的&#xff0c;是给计算机看的。 百度百科定义&#xff1a; 注解&#xff08;Annotation&#xff09;&#xff0c;也叫元数据。一种代码级别的说明。它是JDK1.5及…

FPGA常用IP核之FIFO学习

IP核是FPGA芯片公司提供的逻辑功能块&#xff0c;在FPGA芯片中可以进行优化和预先配置&#xff0c;可以直接在用户设计的程序中使用&#xff0c;应用范围很广。在FPGA设计开发过程中使用IP核&#xff0c;可以大大的缩短开发周期&#xff0c;高度优化的IP核可以使FPG开发工程师专…

8核32G云服务器幻兽帕鲁多人联机主机价格94元/月、1362元一年

8核32G云服务器京东云轻量云主机价格94元1个月、282元3个月、673元6个月、1362元一年&#xff0c;配置8C32G-100G SSD系统盘-10M带宽-2000G月流量 华北-北京&#xff0c;京东云优惠活动 yunfuwuqiba.com/go/jd 活动链接打开如下图&#xff1a; 8核32G云服务器京东云轻量云主机价…

损失函数篇 | YOLOv8更换损失函数之MPDIoU(23年7月首发论文)

前言:Hello大家好,我是小哥谈。损失函数是机器学习中用来衡量模型预测值与真实值之间差异的函数。在训练模型时,我们希望通过不断调整模型参数,使得损失函数的值最小化,从而使得模型的预测值更加接近真实值。不同的损失函数适用于不同的问题,例如均方误差损失函数适用于回…

Codeforces Round 931 (Div. 2) D1. XOR Break — Solo Version

题目 思路&#xff1a; #include <bits/stdc.h> using namespace std; #define int long long #define pb push_back #define fi first #define se second #define lson p << 1 #define rson p << 1 | 1 const int maxn 1e6 5, inf 1e18, maxm 4e4 5; c…

机器学习综述:核心概念、方法与未来展望

一、机器学习基础 基本概念 机器学习是一门专注于开发算法来从数据中学习模式的科学。它基于这样一个假设&#xff1a;如果一个程序可以在某任务T上&#xff0c;基于经验E改善它的性能P&#xff0c;那么我们说这个程序在从经验中学习。这里的“经验”可以理解为历史数据或先前…

腾讯云服务器优惠活动价格表_CPU内存带宽报价明细

2024年最新腾讯云服务器租用优惠价格表&#xff1a;轻量应用服务器2核2G3M价格62元一年、2核2G4M价格118元一年&#xff0c;540元三年、2核4G5M带宽218元一年&#xff0c;2核4G5M带宽756元三年、轻量4核8G12M服务器646元15个月&#xff1b;轻量4核16G12M带宽32元1个月、96元3个…

基于python爬虫与数据分析系统设计

**单片机设计介绍&#xff0c;基于python爬虫与数据分析系统设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于Python爬虫与数据分析系统的设计是一个结合了网络数据抓取、清洗、存储和数据分析的综合项目。这样的系统通常…

【网站项目】三省学堂-学习辅助系统

&#x1f64a;作者简介&#xff1a;拥有多年开发工作经验&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的项目或者毕业设计。 代码可以私聊博主获取。&#x1f339;赠送计算机毕业设计600个选题excel文件&#xff0c;帮助大学选题。赠送开题报告模板&#xff…

Win10 下 Vision Mamba(Vim-main)的环境配置(libcuda.so文件无法找到,windows系统运行失败)

目录 1、下载NVIDIA 驱动程序、cuda11.8、cudnn8.6.0 2、在Anaconda中创建环境并激活 3、下载gpu版本的torch 4、配置环境所需要的包 5、安装causal_conv1d和mamba-1p1p1 安装causal_conv1d 安装mamba-1p1p1 6、运行main.py失败 请直接拉到最后查看运行失败的原因&am…

【C++】vector模拟实现

目录 简介&#xff1a;私有成员&#xff1a;迭代器&#xff1a; 无参构造函数&#xff1a;push_back&#xff1a;reserve&#xff1a;resize:push_back: operator[]重载&#xff1a;begin && end:size && capacity:insert&#xff1a;erase&#xff1a;带参构造…

PyQt ui2py 使用PowerShell将ui文件转为py文件并且将导入模块PyQt或PySide转换为qtpy模块开箱即用

前言 由于需要使用不同的qt环境&#xff08;PySide&#xff0c;PyQt&#xff09;所以写了这个脚本&#xff0c;使用找到的随便一个uic命令去转换ui文件&#xff0c;然后将导入模块换成qtpy这个通用库(支持pyside2-6&#xff0c;pyqt5-6)&#xff0c;老版本的是Qt.py(支持pysid…

论文阅读——Sat2Vid

Sat2Vid: Street-view Panoramic Video Synthesis from a Single Satellite Image 提出了一种新颖的方法&#xff0c;用于从单个卫星图像和摄像机轨迹合成时间和几何一致的街景全景视频。 即根据单个卫星图像和给定的观看位置尽可能真实地、尽可能一致地合成街景全景视频序列。…

Python+Django+Html河道垃圾识别网页系统

程序示例精选 PythonDjangoHtml河道垃圾识别网页系统 如需安装运行环境或远程调试&#xff0c;见文章底部个人QQ名片&#xff0c;由专业技术人员远程协助&#xff01; 前言 这篇博客针对《PythonDjangoHtml河道垃圾识别网页系统》编写代码&#xff0c;代码整洁&#xff0c;规…

如何编写属于自己的第一个exp

0x00 前言 在我们找到一个漏洞之后&#xff0c;可能会想着去fofa上搜语法进而扩大战果&#xff0c;而有些漏洞利用起来十分繁琐&#xff0c;这时候就需要一个exp来批量帮我们进行扫描工作&#xff0c;接下来就介绍一下如何进行exp的编写&#xff0c;这个过程中最重要的还是体现…

Docker简单介绍、特点、与虚拟机技术的区别、核心概念及在CentOS 7 中安装卸载Docker

目录 一、什么是Docker 二、特点 三、Docker与虚拟机技术的区别 四、Docker的核心概念 Docker仓库与仓库注册服务器的区别 五、CentOS7在线安装Docker 安装配置 卸载 一、什么是Docker Docker是一个开源的容器化平台&#xff0c;用于打包、部署和运行应用程序。它利用…

AI设计优化电机、电路与芯片?

一、AI进行电机本体设计 使用AI进行电机本体设计是一种前沿且具有潜力的方法&#xff0c;通过深度学习、强化学习、遗传算法等AI技术&#xff0c;可以实现电机设计的自动化和优化。具体应用可以包括以下几个方面&#xff1a; 此图片来源于网络 1. **参数优化**&#xff1a; …

硬件基础知识

CPU制作 cpu组成原理 CPU (Central Processing Unit - 中央处理单元): CPU 是计算机的核心&#xff0c;负责解释和执行程序指令以及处理数据。它由几个关键部分组成&#xff0c;如算术逻辑单元&#xff08;ALU&#xff09;、寄存器、和控制单元&#xff08;CU&#xff09;&…

游戏攻略|基于Springboot和vue的游戏分享平台系统设计与实现(源码+数据库+文档)

游戏攻略分享平台目录 基于Springboot的在线考试管理系统设计与实现 一、前言 二、系统设计 三、系统功能设计 1、前台&#xff1a; 2、后台 5.2.1管理员功能模块 四、数据库设计 五、核心代码 六、论文参考 七、最新计算机毕设选题推荐 八、源码获取&#xff1a; …

国际体育日,一起运动起来吧

今天是国际体育日&#xff0c;是时候动一动&#xff0c;燃烧我们的卡路里啦&#xff01;说到运动&#xff0c;我得提提最近刚入手华为WATCH GT4&#xff0c;真心不赖&#xff01; 这个手表特别适合喜欢运动的人&#xff0c;它有100的运动模式&#xff0c;无论你是喜欢跑步、…