【笔记】一维动态规划DP

news/2024/12/22 19:53:50/

文章目录

    • 动态规划DP
      • DP解题步骤
      • 例子1
      • lanqiao3367 破损的楼梯
        • 题目描述
        • 输入格式
        • 输出格式
        • 解题思路
        • 代码
      • lanqiao3423 安全序列
        • 题目描述
        • 输入格式
        • 输出格式
        • 解题思路
        • 代码

动态规划DP

动态规划用于解决具有重叠子问题、最优子结构特征的问题。

重叠子问题:子问题是原问题的小版本

最优子结构:大问题的最优解包含小问题的最优解,通过小问题可以推导出大问题

无后效性:“未来与过去无关”,只需要考虑当下如何走到下一步,直接利用结果计算即可,最优子结构满足无后效性。

DP解题步骤

  • 拆分子问题
  • 确定状态:确定状态就是确定问题需要的几个维度的已知变量。一般格式为“前n个x为m的最大价值/最小价值/方案数”
  • 状态转移方程:状态(子问题)之间是如何转移,即一个状态由哪几个状态转移来或者状态可以转移到哪些状态上。
  • 实现:按照循环、记忆化搜索等方程来求解最终状态(答案)

例子1

楼梯有n个台阶,每次可以一步上1阶或者2阶,一共有多少种不同的上楼方法?

原问题:n个台阶的上楼方案数

  • 子问题:n-1个台阶的上楼方案数、n-2个台阶的上楼方案数……
  • 最优子结构:子问题的最优解能否推出原问题的最优解
  • 确定状态:dp[i]表示前i个空位的放置方案数
  • 状态转移方程:要走到第n级台阶,要么从n-1一步走过去,要么从n-2一步走过去。因此,n个台阶的上楼方案数=n-1个台阶的上楼方案数+n-2个台阶的上楼方案数dp[n]=dp[n-1]+dp[n-2]
  • 实现:for循环实现
"""
台阶编号:到达这个台阶的最大方案数
1:1
2:1+1,2
3:1+1+1,2+1,1+2
......
dp[n]=dp[n-1]+dp[n-2]
dp[1]=1
dp[2]=2
"""
n=int(input())
dp=[0]*(n+1)
dp[1]=1
dp[2]=2
for i in range(3,n+1):dp[i]=dp[i-1]+dp[i-2]
print(dp[n])

lanqiao3367 破损的楼梯

题目描述

共有N级台阶,从第0级出发,每次可以迈1阶或者2阶,但是楼梯上的第a1、a2、a3…共M级台阶已经坏了,不能踩上去。

问想要到达楼梯的顶端但不踩破损的台阶,有多少种方案?
由于方案数很大,故输出其对 10 e 9 + 7 10e^9+7 10e9+7取模的结果。

输入格式

第一行:两个整数N,M

第二行:包含M个正整数,表示坏掉的台阶编号

输出格式

输出一个整数

解题思路

这题和上面的例题的差别在于多出了坏掉的台阶,用一个数组vis[n]来 标记坏掉的台阶。
via[i]==1表示第i个台阶坏掉了
via[i]==0表示第i个台阶没有坏

via[i]==1,我们不能踩这个台阶,那么对于第i+1个台阶的方案数就不包含dp[i-1]只有dp[i-2],初始化的时候,dp[i-1]为0,dp[i]=dp[i-2],dp[i+1]=dp[i]+dp[i-1]=dp[i-2]+dp[i-1],所以可以直接continue当遇到via[i]==1

代码
n,m=map(int,input().split())
a=list(map(int,input().split()))
dp=[0]*(n+1)
vis=[0]*(n+1)
for i in a:vis[i]=1
dp[0]=1
dp[1]=1-vis[1]
for i in range(2,n+1):if vis[i]==1:continuedp[i]=(dp[i-1]+dp[i-2])%1000000007
print(dp[n]) 

lanqiao3423 安全序列

题目描述

在一条直线上的n个空位放置若干个油桶,每2个油桶之间需间隔k个空位,有多少种放油桶的方式?

输出结果对 10 e 9 + 7 10e^9+7 10e9+7取模

输入格式

第一行:两个正整数n,k

输出格式

输出1个整数,表示方案数对 10 e 9 + 7 10e^9+7 10e9+7取模

解题思路

状态:dp[i]表示前i个空位的放置方案数

状态转移:dp[i]考虑两种情况

第i个空位不放油桶:从dp[i-1]转移第i个空位放置油桶:从dp[i-k-1]转移

dp[i]=dp[i-1]+(i-k-1>=0?)dp[i-k-1]

代码
mod=1000000007
n,k=map(int,input().split())
dp=[0]*(n+1)
#初始化:一个桶都不放是一种方案
dp[0]=1
for i in range(1,n+1):#放置if i-k-1>=0:dp[i]=(dp[i-k-1]+dp[i-1])%mod#不放置,还要加上如果前面都不放只在这个位置放的一种可能else:dp[i]=(dp[i-1]+1)%mod
print(dp[n]) 

http://www.ppmy.cn/news/1524427.html

相关文章

安装与pytorch不同cuda版本的bitsandbytes

由于历史遗留问题,虽然我的cuda版本是11.8,但是我的torch对应cuda版本是12.1,安装bitsandbytes后,就会抛出以下报错: Could not load bitsandbytes native library: libcusparse.so.12: cannot open shared object fi…

Flask如何传递URL参数

在Flask中,传递URL参数是一种常见且强大的功能,它允许你的Web应用根据URL中的不同部分来动态地生成内容或执行不同的操作。虽然直接撰写5000字来详细解释这一功能可能过于冗长,但我可以提供一个简明而全面的概述,包括基本概念、使…

ISAC: Toward Dual-Functional Wireless Networks for 6G and Beyond【论文阅读笔记】

此系列是本人阅读论文过程中的简单笔记,比较随意且具有严重的偏向性(偏向自己研究方向和感兴趣的),随缘分享,共同进步~ Integrated Sensing and Communications: Toward Dual-Functional Wireless Networks for 6G and…

AI客服机器人开启企业客户服务新纪元

随着人工智能(AI)技术的迅猛发展,使得AI客服机器人走进了我们的视野,成为提高客户满意度和业务效率的不二法宝。这些智能机器人不仅能够处理海量信息,还能为客户提供个性化的服务体验。 一、AI客服机器人的基本原理 AI客服机器人是基于人工智…

探索非局部均值滤波在椒盐噪声去除中的应用

在图像处理领域,椒盐噪声是一种常见的干扰,它会导致图像出现随机的黑白像素点,严重影响图像质量。为了解决这一问题,本文将介绍一种有效的去噪技术——非局部均值滤波(NLM)的改进版本,即NAMF&am…

Java面试篇基础部分-JVM详细介绍

JVM的运行机制 JVM(Java Virtual Machine)是用于运行Java字节码的虚拟计算机,其中包括一套字节码的指令集、程序寄存器、虚拟机栈、虚拟机堆、本地方法区、垃圾回收器。JVM运行在操作系统上层,它不跟底层硬件直接进行交互。如下图所示   Java源代码通过了编译器编译成响…

电商品牌假货要怎么处理

在电商蓬勃发展的今日,假货问题如影随形,严重威胁着品牌的声誉与市场的健康。力维网络以专业打假服务,为品牌保驾护航。 一、精准监测,揪出假货端倪 力维网络的数据监测系统犹如一张严密的大网,覆盖全网。通过全面采集…

Linux中限制服务如mysql的最大cpu使用率

1、cpu占用测试&#xff1a; DELIMITER // DROP PROCEDURE IF EXISTS intensive_calculations; CREATE PROCEDURE intensive_calculations() BEGINDECLARE v INT DEFAULT 0;DECLARE i INT DEFAULT 0;WHILE i < 1000000 DOSET v SQRT(i * i (RAND() * 10000));SET i i 1…