【笔记】一维动态规划DP

embedded/2024/9/24 1:04:12/

文章目录

    • 动态规划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/embedded/113105.html

相关文章

FastAPI与环境变量:实现无缝切换与高效运维

在现代软件开发中,尤其是构建RESTful API时,环境变量的管理显得尤为重要。它们不仅允许我们在不同环境中(如开发、测试、生产)灵活地调整应用的行为,还极大地增强了应用的安全性和可维护性。FastAPI作为一个新兴的、高…

SpringBoot3整合ELK实现日志可视化

SpringBoot整合ELK实现日志可视化 一、环境准备 Elasticsearch、Logstash、Kibana,组合起来可以搭建线上日志系统 ELK中各个服务的作用 Elasticsearch:用于存储收集到的日志信息; Logstash:用于收集日志,SpringBoot应用整合了Logstash以后会把日志发…

OpenCV高阶操作

在图像处理与计算机视觉领域,OpenCV(Open Source Computer Vision Library)无疑是最为强大且广泛使用的工具之一。从基础的图像读取、 1.图片的上下,采样 下采样(Downsampling) 下采样通常用于减小图像的…

Redis命令:redis-cli

Redis 命令用于在 redis 服务上执行操作。 要在 redis 服务上执行命令需要一个 redis 客户端。Redis 客户端在我们之前下载的的 redis 的安装包中。 语法 Redis 客户端的基本语法为: $ redis-cli 实例 以下实例讲解了如何启动 redis 客户端: 启动…

【C++ Primer Plus习题】16.3

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: #include <iostream> #include <string> #include <…

【贪心算法】贪心算法

贪心算法简介 1.什么是贪心算法2.贪心算法的特点3.学习贪心的方向 点赞&#x1f44d;&#x1f44d;收藏&#x1f31f;&#x1f31f;关注&#x1f496;&#x1f496; 你的支持是对我最大的鼓励&#xff0c;我们一起努力吧!&#x1f603;&#x1f603; 1.什么是贪心算法 与其说是…

初学Linux(学习笔记)

初学Linux&#xff08;学习笔记&#xff09; 前言 本文跳过了Linux前期的环境准备&#xff0c;直接从知识点和指令开始。 知识点&#xff1a; 1.目录文件夹&#xff08;Windows&#xff09; 2.文件内容属性 3.在Windows当中区分文件类型是通过后缀&#xff0c;而Linux是通过…

排队免单模式小程序开发

开发一个排队免单模式的小程序涉及多个方面&#xff0c;包括需求分析、界面设计、后端开发、数据库设计以及测试上线等。下面我将详细介绍每个步骤的概要&#xff1a; 1.需求分析 明确目标&#xff1a;首先确定小程序的核心功能&#xff0c;即排队免单模式的具体实现方式。例如…