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

动态规划基础

动态规划

1、动态规划的概念

        简称DP,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。常常适用于有重叠子问题和最优子结构性质的问题。

        简单来说,就是给定一个问题,把它拆成一个个子问题,查到子问题可以直接解决。然后把子问题答案保存起来,以减少重复计算。再根据子问题答案反推,得出原问题解的一种方法。

核心思想在于拆分子问题,记住过往,减少重复计算。

2、动态规划的步骤

  1. 划分子问题
  2. 状态表示,一般用数组dp[i]表示当前状态
  3. 状态转移,即当前状态是由前面那些状态转移过来的,例如dp[i]=dp[i-1],表示当前状态可以由上一个状态转移过来
  4. 确定边界,确定初始状态

一、线性DP

1、线性DP的概念

        动态规划中的一类问题,指状态之间有线性关系的动态规划问题。所谓线性DP,就是递推方程是有一个明显的线性关系的,一维线性和二维线性都有可能。在求的时候,一行一行地来求

例题----取钱

        https://www.lanqiao.cn/problems/3297/learning/

        黄开的银行最近又发行了一种新面额的钞票面值为4,所以现在黄有5种面额的钞票,分别是20,10,5,4,1。但是不变的是他小气,现在又有很多人来取钱,黄又不开心了,请人来取钱,黄又不开心了,请你算出每个来取钱的人黄应该给他至少多少张钞票。

输入格式:每个测评数据含有不超过10组输入,每组给出一个n(1<=n<=10000),n为要取出的金额。

输出格式:每组样例输出一个答案(钞票数)。

示例:20                                     1

           2                                       2

           6                                       2

提示:

        设置dp[i]数组 取出金额为i

        最小钞票数 转移方程为:dp[i]=Math.min(dp[i-1],dp[i-4],dp[i-5],dp[i-10],dp[i-20])+1

import java.util.Arrays;
import java.util.Scanner;public class Main {
public static void main(String[] args) {Scanner sc = new Scanner(System.in);int[] arr = { 1, 4, 5, 10, 20 };int[] dp = new int[10001]; // 索引为金额, 值为方案数Arrays.fill(dp, 10000);dp[0] = 0; // 0金额的可选方案数量为0个for (int i = 1; i < dp.length; ++i) { // 枚举子问题金额数for (int j : arr) { // 每个子问题可选方案if (i >= j) { // 当金额大于等于面额时dp[i] = Math.min(dp[i - j] + 1, dp[i]); // 选择当前面额后 +1,且寻找剩余金额时方案数累加,与当前j之后的面额继续对比方案数}}}while (sc.hasNext()) {System.out.println(dp[sc.nextInt()]);}}
}

例题---破损的楼梯

https://www.lanqiao.cn/problems/3367/learning/

        小蓝来到了一座高耸的楼提前,楼梯共有N级台阶,从第0级台阶出发。小蓝每次可以迈上1级或2级台阶。但是,楼梯上的第a_{1}级,第a_{2}级,第a_{3}级,以此类推,共m级台阶的台阶面已经坏了,不能踩上去。

        现在,小蓝想要到达楼梯的顶端,也就是第N级台阶,但他不能踩到坏了的台阶上。请问他有多少种不踩坏了的台阶到达顶端的方案数?由于方案数很大,请输入其对10^{9}+7取模的结果。

输入格式:

        第一行包含两个正整数N(1<=N<=10^{5})和M(0<=M<=N),表示楼梯的总级数和坏了的台阶数。

        接下来一行,包含M个正整数

相关文章:

动态规划基础

动态规划 1、动态规划的概念 简称DP,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。常常适用于有重叠子问题和最优子结构性质的问题。 简单来说,就是给定一个问题,把它拆成一个个子问题,查到子问题可以直接解决。然后把子问题答案保存起来,以减少重复计算…...

kubeadm部署的k8s1.29集群证书更新

1、查看证书有效期 kubeadm certs check-expiration更新证书前&#xff1a; [check-expiration] Reading configuration from the cluster... [check-expiration] FYI: You can look at this config file with kubectl -n kube-system get cm kubeadm-config -o yamlCERTIFIC…...

【A 类比赛】大学生学科竞赛智慧应用场景题目大全

智能应用的多彩场景&#xff1a;未来生活的无限可能 随着科技的飞速发展&#xff0c;智能应用已经渗透到我们生活的方方面面&#xff0c;它们不仅极大地提高了工作效率&#xff0c;也丰富了我们的生活体验。从家庭到工作场所&#xff0c;从城市到乡村&#xff0c;智能应用正在…...

Yarn的安装和使用(2):使用及问题解决

Yarn是JavaScript的依赖管理工具&#xff0c;它与npm类似&#xff0c;但提供了一些额外的性能优化和一致性保证。 Yarn的使用&#xff1a; 初始化项目&#xff1a; yarn init 此命令会引导您创建一个新的package.json文件&#xff0c;用于记录项目的元信息和依赖。 添加依赖&…...

如何在Bash中连接字符串变量

问题&#xff1a; 在 PHP 中&#xff0c;字符串按如下方式连接在一起&#xff1a; $foo "Hello"; $foo . " World";在这里&#xff0c;$foo 变成了 "Hello World"。 在 Bash 中如何实现这一点? 回答1&#xff1a; foo"Hello" fo…...

doesn‘t contain a valid partition table

查看硬盘空间 $ fdisk -l Disk /dev/mmcblk0: 29 GB, 31037849600 bytes, 60620800 sectors 947200 cylinders, 4 heads, 16 sectors/track Units: sectors of 1 * 512 512 bytesDisk /dev/mmcblk0 doesnt contain a valid partition table Disk /dev/mmcblk0p1: 1 MB, 10485…...

modprobe加载驱动模块时报错:modprobe: module xxx.ko not found in modules.dep

问题 使用modprobe时&#xff0c;报错modprobe: module xxx.ko not found in modules.dep&#xff1a; 原因 加载模块时&#xff0c;依赖没法正确添加 解决 在使用modprobe前&#xff0c;调用一下depmod指令&#xff0c;之后再用modprobe加载驱动模块 depmod modprobe interr…...

游戏引擎中的粒子系统

一、粒子基础 粒子系统里有各种发射器&#xff08;emitter&#xff09;&#xff0c;发射器发射粒子&#xff08;particle&#xff09;。 粒子是拥有位置、速度、大小尺寸、颜色和生命周期的3D模型。 粒子的生命周期中&#xff0c;包含产生&#xff08;Spawn&#xff09;、与环…...

哈佛大学商业评论 -- 第二篇:增强现实是如何工作的?

AR将全面融入公司发展战略&#xff01; AR将成为人类和机器之间的新接口&#xff01; AR将成为人类的关键技术之一&#xff01; 请将此文转发给您的老板&#xff01; --- 本文作者&#xff1a;Michael E.Porter和James E.Heppelmann 虽然物理世界是三维的&#xff0c;但大…...

『python爬虫』巨量http代理使用 每天白嫖1000ip(保姆级图文)

目录 注册 实名得到API链接和账密 Python3requests调用Scpay总结 欢迎关注 『python爬虫』 专栏&#xff0c;持续更新中 欢迎关注 『python爬虫』 专栏&#xff0c;持续更新中 注册 实名 注册巨量http 用户概览中领取1000ip,在动态代理中使用.用来测试一下还是不错的 得到AP…...

6-95 希尔排序(Java语言描述)

编程实现希尔排序函数。public static void shellSort(int arr[])。其中arr存放待排序的数据,数组长度不大于1000。 函数接口定义: /* 对长度为n的数组arr执行希尔排序 */ public static void shellSort(int arr[]); 请实现 shellSort函数,使排序后的数据从小到大排列。…...

JAVA面试大全之分布式篇

目录 1、一致性算法 1.1、什么是分布式系统的副本一致性?有哪些? 1.2、在分布式系统中有哪些常见的一致性算法?...

qt各种锁使用讲解

在Qt中&#xff0c;主要有以下几种锁的类型&#xff1a; 1. QMutex&#xff08;互斥锁&#xff09;&#xff1a; 是最常见的锁类型&#xff0c;用于实现简单的互斥访问。可以通过lock()和unlock()手动控制锁的加锁和解锁。 QMutexLocker&#xff1a;是一个RAII类&#xff0c;…...

5.111 BCC工具之ext4dist.py解读

一,工具简介 ext4dist跟踪ext4的读取、写入、打开和fsync操作,并将其延迟总结为2的幂次方直方图。 二,代码示例 #!/usr/bin/env pythonfrom __future__ import print_function from bcc import BPF from time import sleep, strftime import argparse# symbols kallsyms …...

Rust 的 termion 库控制终端光标的位置

在控制台应用程序中&#xff0c;固定打印在屏幕的第一行通常涉及到控制终端光标的位置。Rust 标准库本身并不提供直接控制终端光标位置的功能&#xff0c;但你可以使用第三方库如 termion 来实现这个需求。 termion 是一个用于处理终端的 Rust 库&#xff0c;它提供了很多有用…...

ADB(Android Debug Bridge)操作命令详解及示例

ADB&#xff08;Android Debug Bridge&#xff09;是一个强大的命令行工具&#xff0c;它是Android SDK的一部分&#xff0c;主要用于Android设备&#xff08;包括真实手机和平板电脑以及模拟器&#xff09;的调试、系统控制和应用程序部署。 下面是一些ADB的常用命令&#xff…...

书生浦语训练营2期-第二节课笔记作业

目录 一、前置准备 1.1 电脑操作系统&#xff1a;windows 11 1.2 前置服务安装&#xff08;避免访问127.0.0.1被拒绝&#xff09; 1.2.1 iis安装并重启 1.2.2 openssh安装 1.2.3 openssh服务更改为自动模式 1.2.4 书生浦语平台 ssh配置 1.3 补充&#xff08;前置服务ok…...

【日常积累】指定ruby版本环境安装

背景说明 在redis的5.0版本之前&#xff0c;使用redis提供的redis-trib创建redis集群时还需要依赖ruby环境。当然有时候我们自已也需要安装指定ruby版本环境。下面是安装时的大致过程&#xff0c;以及过程中遇到的问题解决。我使用的环境是centos7&#xff0c;小版本差别应该不…...

SOC内部集成网络MAC外设+ PHY网络芯片方案:MII/RMII 接口与 MDIO 接口

一. 简介 本文来了解一下常用的一种网络硬件方案&#xff1a;SOC内部集成网络MAC外设 PHY网络芯片方案。 其中涉及的 MII接口&#xff0c;RMII接口&#xff08;MII接口与RMII接口二选一&#xff09;&#xff0c;MDIO接口&#xff0c;RJ45。 二. MII/RMII 接口&#xff0c;M…...

简单了解HTTP和HTTPS

HTTP的安全问题&#xff1f; 我们都知道HTTP是不安全的&#xff0c;而HTTPS是安全的&#xff0c;那HTTP有哪些安全问题呢&#xff1f;&#xff08;考虑传输过程以及响应方&#xff09; 明文传输&#xff0c;有窃听风险&#xff1a;HTTP协议无法加密数据&#xff0c;所有通信数…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

解决:Android studio 编译后报错\app\src\main\cpp\CMakeLists.txt‘ to exist

现象&#xff1a; android studio报错&#xff1a; [CXX1409] D:\GitLab\xxxxx\app.cxx\Debug\3f3w4y1i\arm64-v8a\android_gradle_build.json : expected buildFiles file ‘D:\GitLab\xxxxx\app\src\main\cpp\CMakeLists.txt’ to exist 解决&#xff1a; 不要动CMakeLists.…...

【51单片机】4. 模块化编程与LCD1602Debug

1. 什么是模块化编程 传统编程会将所有函数放在main.c中&#xff0c;如果使用的模块多&#xff0c;一个文件内会有很多代码&#xff0c;不利于组织和管理 模块化编程则是将各个模块的代码放在不同的.c文件里&#xff0c;在.h文件里提供外部可调用函数声明&#xff0c;其他.c文…...

如何通过git命令查看项目连接的仓库地址?

要通过 Git 命令查看项目连接的仓库地址&#xff0c;您可以使用以下几种方法&#xff1a; 1. 查看所有远程仓库地址 使用 git remote -v 命令&#xff0c;它会显示项目中配置的所有远程仓库及其对应的 URL&#xff1a; git remote -v输出示例&#xff1a; origin https://…...

在Zenodo下载文件 用到googlecolab googledrive

方法&#xff1a;Figshare/Zenodo上的数据/文件下载不下来&#xff1f;尝试利用Google Colab &#xff1a;https://zhuanlan.zhihu.com/p/1898503078782674027 参考&#xff1a; 通过Colab&谷歌云下载Figshare数据&#xff0c;超级实用&#xff01;&#xff01;&#xff0…...

21-Oracle 23 ai-Automatic SQL Plan Management(SPM)

小伙伴们&#xff0c;有没有迁移数据库完毕后或是突然某一天在同一个实例上同样的SQL&#xff0c; 性能不一样了、业务反馈卡顿、业务超时等各种匪夷所思的现状。 于是SPM定位开始&#xff0c;OCM考试中SPM必考。 其他的AWR、ASH、SQLHC、SQLT、SQL profile等换作下一个话题…...