当前位置: 首页 > news >正文

动态规划【Day01】| 669 · 换硬币、114 · 不同的路径、116 · 跳跃游戏

秘诀:确定状态+转移方程+初始条件和边界情况+计算顺序

669 · 换硬币

669 · 换硬币
题目描述:
给出不同面额的硬币以及一个总金额. 写一个方法来计算给出的总金额可以换取的最少的硬币数量. 如果已有硬币的任意组合均无法与总金额面额相等, 那么返回 -1。

样例1
输入:
[1, 2, 5]
11
输出: 3
解释: 11 = 5 + 5 + 1

样例2
输入:
[2]
3
输出: -1

样例3
输入:
[1, 9]
0
输出: 0

举例:有面值为2,5,7三种硬币,找出能够使用最少硬币组合成总额为27的方案?

首先来看看使用递归的问题——做了很多重复计算,效率低下
在这里插入图片描述

在这里插入图片描述

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

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

在这里插入图片描述

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

public class Solution {/*** @param coins: a list of integer* @param amount: a total amount of money amount* @return: the fewest number of coins that you need to make up*/public int coinChange(int[] coins, int amount) {int num = coins.length; //the num of given coinsint[] f = new int[amount+1]; //0...amountf[0] = 0; //initfor (int remainValue = 1; remainValue <= amount; remainValue++) {f[remainValue] = Integer.MAX_VALUE;//select last coin(each choice will consider n coins)for (int i = 0; i < num; i++) {if (remainValue >= coins[i] && f[remainValue-coins[i]] != Integer.MAX_VALUE && f[remainValue-coins[i]]+1<f[remainValue]) {f[remainValue] = f[remainValue-coins[i]]+1;}}}if (f[amount] == Integer.MAX_VALUE) {return -1;}return f[amount];}
}

感觉数组下标还是用i,j比较直观,具体含义心中有数即可。


114 · 不同的路径

114 · 不同的路径
题目描述:
有一个机器人位于一个 m×n 网格的左上角。

机器人每一时刻只能向下或者向右移动一步。机器人试图达到网格的右下角。

问有多少条不同的路径?

样例 1:
输入:
n = 1
m = 3
输出:
1
解释:
只有一条通往目标位置的路径。

样例 2:
输入:
n = 3
m = 3
输出:
6
解释:
D : Down
R : Right
DDRR
DRDR
DRRD
RRDD
RDRD
RDDR
在这里插入图片描述

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

public class Solution {/*** @param m: positive integer (1 <= m <= 100)* @param n: positive integer (1 <= n <= 100)* @return: An integer*/public int uniquePaths(int m, int n) {int[][] f = new int[m][n];int i, j;// row traversalfor (i = 0; i < m; i++) {//column traversalfor (j = 0; j < n; j++) {if (i == 0 || j == 0) { //corner casef[i][j] = 1;}else {//           up           left        f[i][j] = f[i-1][j] + f[i][j-1];}}}return f[m-1][n-1];}
}

116 · 跳跃游戏

116 · 跳跃游戏
题目描述:
给出一个非负整数数组,你最初定位在数组的第一个位置。

数组中的每个元素代表你在那个位置可以跳跃的最大长度。

判断你是否能到达数组的最后一个位置。

注:数组中的元素代表着青蛙在当前石头能跳的最大距离,而不是说一定要跳这么多。

样例 1:
输入:
A = [2,3,1,1,4]
输出:
true
解释:
0 -> 1 -> 4(这里的数字为下标)是一种合理的方案。

样例 2:
输入:
A = [3,2,1,0,4]
输出:
false
解释:
不存在任何方案能够到达终点。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

public class Solution {/*** @param a: A list of integers* @return: A boolean*/public boolean canJump(int[] a) {if (a == null || a.length == 0) {return false;}int n = a.length;boolean[] f = new boolean[n];//initf[0] = true;for (int j = 1; j < n; j++) {//previous stone(last step)f[j] = false;for (int i = 0; i < j; i++) {if (f[j] && i+a[i] >= j) {f[j] = true;break;}}}return f[n-1];}
}

注:一个细节需要注意一下,数组可以为空,也可以长度为0

今日小结

在这里插入图片描述

在这里插入图片描述

相关文章:

动态规划【Day01】| 669 · 换硬币、114 · 不同的路径、116 · 跳跃游戏

秘诀&#xff1a;确定状态转移方程初始条件和边界情况计算顺序 669 换硬币 669 换硬币 题目描述&#xff1a; 给出不同面额的硬币以及一个总金额. 写一个方法来计算给出的总金额可以换取的最少的硬币数量. 如果已有硬币的任意组合均无法与总金额面额相等, 那么返回 -1。 样…...

1.Hello Python

Python ​ Python 在网络爬虫、数据分析、AI、机器学习、Web开发、金融、运维、测试等多个领域都有不俗的表现&#xff0c;从来没有哪一种语言可以同时在这么多领域扎根。 Python基本语法 python关键字 ​ 关键字即保留字&#xff0c;和其他语言一样&#xff0c;这些关键字…...

C语言实例|编写C程序在控制台打印余弦曲线

C语言文章更新目录 C语言学习资源汇总&#xff0c;史上最全面总结&#xff0c;没有之一 C/C学习资源&#xff08;百度云盘链接&#xff09; 计算机二级资料&#xff08;过级专用&#xff09; C语言学习路线&#xff08;从入门到实战&#xff09; 编写C语言程序的7个步骤和编程…...

《Hadoop篇》------大数据及Hadoop入门

目录 一、大数据及Hadoop入门 1.1 单节点、分布式、集群 1.1.1 大数据的概念 1.1.2 大数据的本质 二、HDFS Shell命令 2.1、常用相关命令 2.2、上传文件 2.2.1、上传文件介绍 2.2.2上传文件操作 2.3、下载文件 2.4、删除文件 2.5、创建目录 2.6、查看文件系统 2.…...

TCP核心机制详解(三)

目录 前言&#xff1a; 滑动窗口 滑动窗口处理丢包问题 流量控制 拥塞控制 延时应答 捎带应答 面向字节流 异常情况 小结&#xff1a; 前言&#xff1a; 前两篇文章讲述了&#xff0c;TCP十种核心机制的前三种。这篇文章详细介绍其他的一些核心机制&#xff0c;让我们…...

最易上手的爬虫请求库:Requests核心功能速览(下)

上一个章节我们讲了如何快速使用Requests发送网络请求、处理URL参数和提取响应内容,这些是最基本的操作。 然而还有很多场景下,我们的网络请求更加复杂。比如我们必须要定制请求头来假装成浏览器,不然可能会被网站识别为机器并且被屏蔽;又比如我们需要在发送请求时以表单形…...

生产故障|Kafka ISR频繁伸缩引发性能急剧下降

生产故障&#xff5c;Kafka ISR频繁伸缩引发性能急剧下降-阿里云开发者社区 本文是笔者双十一系列第二弹&#xff0c;源于一个双十一期间一个让笔者猝不及防的生产故障&#xff0c;本文将详细剖析Kafka的副本机制&#xff0c;以及ISR频繁变更(扩张与伸缩)为什么会导致集群不可…...

c++终极螺旋丸:₍˄·͈༝·͈˄*₎◞ ̑̑“类与对象的结束“是结束也是开始

文章目录 前言一.构造函数中的初始化列表 拷贝对象时的一些编译器优化二.static成员三.友元四.内部类总结前言 前两期我们将类和对象的重点讲的差不多了&#xff0c;这一篇文章主要进行收尾工作将类和对象其他的知识点拉出来梳理一遍&#xff0c;并且补充前两篇没有讲过的…...

【Python--torch.nn.functional】F.normalize用法 + 代码说明

【Python–torch.nn.functional】F.normalize介绍 代码说明 文章目录【Python--torch.nn.functional】F.normalize介绍 代码说明1. 介绍2. 代码说明2.1 一维Tensor2.2 二维Tensor2.3 三维Tensor3. 总结1. 介绍 import torch.nn.functional as F F.normalize(input: Tensor, …...

【算法题】1887. 使数组元素相等的减少操作次数

插&#xff1a; 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。点击跳转到网站。 坚持不懈&#xff0c;越努力越幸运&#xff0c;大家一起学习鸭~~~ 题目&#xff1a; 给你一个整数数组 nums &#xff0…...

GD库图片裁剪指定形状解决办法(PHP GD库 海报)

需求描述&#xff1a;需要把图片裁剪成一个指定的平行四边形&#xff0c;目的是使用GD库&#xff0c;把裁剪后的图片放在底图上面&#xff0c;使最终合成的图片看起来是一个底图平行四边形的样子提示&#xff1a;可以结合本作者的其他文章&#xff0c;来生成一个定制化的海报&a…...

redis的简介及应用场景

1、基本信息 Redis英文官网介绍&#xff1a; Redis is an open source (BSD licensed), in-memory data structure store, used as a database, cache and message broker. It supports data structures such as strings, hashes, lists, sets, sorted sets with range queri…...

2、HAL库利用滴答定时器systick(1ms中断)实现时间计数戳

文档说明&#xff1a;通过滴答定时器的1ms中断实现时间计数&#xff0c;标记需要的时间标志&#xff0c;在主函数中查询标志&#xff0c;避免延时函数消耗CPU 1、HAL库systick定时器说明 在CubeMx生成的代码main()函数首先执行的函数为HAL_Init();里面会进行滴答定时器初始化…...

Spring入门学习

Spring入门学习 文章目录Spring入门学习Spring概述Spring FrameworkIOCIOC容器DIIOC容器的实现类①FileSystemXmlApplicationContext②ClassPathXmlApplicationContext基于XML管理bean入门案例创建类创建xml在Spring配置文件中配置bean测试Spring概述 Spring 是最受欢迎的企业级…...

webpack(4版本)使用

webpack简介&#xff1a;webpack 是一种前端资源构建工具&#xff0c;一个静态模块打包器(module bundler)。在 webpack 看来, 前端的所有资源文件(js/json/css/img/less/...)都会作为模块处理。它将根据模块的依赖关系进行静态分析&#xff0c;打包生成对应的静态资源(bundle)…...

Linux安装ElasticSearch

下载地址&#xff1a;https://www.elastic.co/cn/downloads/past-releases#elasticsearch 1 版本选择 ElasticSearch 7 及以上版本都是自带的 jdk&#xff0c;假如需要配置指定的 jdk 版本的话&#xff0c;可以在 es 的 bin 目录下找到elasticsearch-env.bat 这个文件&#x…...

Linux中C语言编程经验总结

​ 修改记录 版本号日期更改理由V1.02022-03-15MD化 总则 仅总结一些常用且实用的编程规范和技巧&#xff0c;且避免记忆负担&#xff0c;聚焦影响比较大的20% ! 编译器 打开全warning编译器开关 正例 gcc -W -Wall -g -o someProc main.c反例 gcc -g -o someProc main…...

jvisualvm工具使用

jdk自带的工具jvisualvm&#xff0c;可以分析java内存使用情况&#xff0c;jvm相关的信息。 1、设置jvm启动参数 设置jvm参数**-Xms20m -Xmx20m -XX:PrintGCDetails** 最小和最大堆内存&#xff0c;打印gc详情 2、测试代码 TestScheduleClassGc package com.core.schedule;…...

redis五大IO网络模型、内存回收

目录1.0用户空间和内核态空间1.1 网络模型-阻塞IO1.2 网络模型-非阻塞IO1.3 网络模型-IO多路复用1.3.1 网络模型-IO多路复用-select方式1.3.2 网络模型-IO多路复用模型-poll模式1.3.3 网络模型-IO多路复用模型-epoll函数1.3.4 网络模型-epoll中的ET和LT1.3.5 网络模型-基于epol…...

【C/C++】内存管理详解

目录内存布局思维导图1.C/C内存分布数据段&#xff1a;栈&#xff1a;代码段&#xff1a;堆:2.C语言中动态内存管理方式3.C内存管理方式3.1new/delete操作内置类型3.2new和delete操作自定义类型4.operator new 与 operator delete函数5.new和delete的实现原理5.1内置类型5.2自定…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...