题目 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，导弹数不超过1000），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。输入格式共一行，输入导弹依次飞来的高度。输出格式第一行包含一个整数，表示最多能拦截的导弹数。第二行包含一个整数，表示要拦截所有导弹最少要配备的系统数

文章目录前言LeetCode、746.使用最小花费爬楼梯【简单，动态规划线性DP】题目与分类思路资料获取前言博主介绍：✌目前全网粉丝2W+，csdn博客专家、Java领域优质创作者，博客之星、阿里云平台优质作者、专注于Java后端技术领域。涵盖技术内容：Java后端、算法、分布式微服务、中间件、前端、运维、ROS等。博主所有博客文件目录索引：博客目录索引(持续更新)视频平台：b站-Coder长路LeetCode、746.使用最小花费爬楼梯【简单，动态规划线性DP】题目与分类题目链接：LeetCode、746.使用最小花费爬楼梯【简单，动态规划线性DP】题目类型：动态规划/线性DP（一维DP）思

文章目录前言LeetCode、198.打家劫舍【中等，一维线性DP】题目及分类思路线性DP（一维）资料获取前言博主介绍：✌目前全网粉丝2W+，csdn博客专家、Java领域优质创作者，博客之星、阿里云平台优质作者、专注于Java后端技术领域。涵盖技术内容：Java后端、算法、分布式微服务、中间件、前端、运维、ROS等。博主所有博客文件目录索引：博客目录索引(持续更新)视频平台：b站-Coder长路LeetCode、198.打家劫舍【中等，一维线性DP】题目及分类题目链接：LeetCode、198.打家劫舍分类：动态规划/线性DP思路线性DP（一维）思路说明：首先抓住条件：①无法同时偷连续的两所

线性DP——花店橱窗谨以此题解献给线性dp最后一道题题目大致Descriptionxq和他的老婆xz最近开了一家花店，他们准备把店里最好看的花都摆在橱窗里。但是他们有很多花瓶，每个花瓶都具有各自的特点，因此，当各个花瓶中放入不同的花束时，会产生不同的美学效果。为了使橱窗里的花摆放的最合适，他们得想个办法安排每种花的摆放位置。可是因为xq和xz每天都太忙，没有时间设计橱窗里花的摆法，所以他们想让你帮他们求出花摆放的最大美观程度和每种花所放的位置。注：标号小花必须放在标号大的前面。每种花放在不同的瓶子里会产生不同的美观程度，美观程度可能是正数也可能是负数。上述例子中，花瓶与花束的不同搭配所具有的美

参考-代码随想录在讲解背包问题的时候，我们都是按照如下五部来逐步分析，相信大家也体会到，把这五部都搞透了，算是对动规来理解深入了。确定dp数组（dptable）以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组背包递推公式问能否能装满背包（或者最多装多少）：dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);，对应题目如下：动态规划：416.分割等和子集动态规划：1049.最后一块石头的重量II问装满背包有几种方法：dp[j]+=dp[j-nums[i]]，对应题目如下：动态规划：494.目标和动态规划：518.零钱兑换II动态规划：377.组合

背包问题总结后期写背包问题介绍 1.01背包有n件物品和一个最多能背重量为w的背包。第i件物品的重量是weight[i]，得到的价值是value[i]。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。每一件物品其实只有两个状态，取或者不取，所以可以使用回溯法搜索出所有的情况，那么时间复杂度就是o(2^n)，这里的n表示物品数量。所以暴力的解法是指数级别的时间复杂度。进而才需要动态规划的解法来进行优化！ 1.1二维dp数组01背包第一步要明确两点，「状态」和「选择」。先说状态，如何才能描述一个问题局面？只要给几个物品和一个背包的容量限制，就形成了一个背包问题呀。所以状态有两个，就是

文章目录139.单词拆分1.dp含义2.递推3.初始化4.遍历顺序198.打家劫舍1.dp含义2.递推3.初始化4.遍历顺序213.打家劫舍Ⅱ337.打家劫舍Ⅲ121.买卖股票的最佳时机贪心算法动态规划1.dp含义2.递推3.初始化4.遍历顺序122.买卖股票的最佳时机Ⅱ123.买卖股票的最佳时机Ⅲ1.确定dp数组以及下标的含义2.递推公式dp[i][0]dp[i][1]：第一次持有dp[i][2]：第一次不持有dp[i][3]：第二次持有dp[i][4]：第二次不持有3.初始化188.买卖股票的最佳时机Ⅳ309.买卖股票的最佳时机含冷冻期**1.确定dp数组以及下标的含义**2.递推dp[i

作者推荐视频算法专题本文涉及知识点动态规划汇总LeetCode:233数字1的个数给定一个整数n，计算所有小于等于n的非负整数中数字1出现的个数。示例1：输入：n=13输出：6示例2：输入：n=0输出：0提示：09数位dp的封装类本题比较简单，主要讲封装类。m_vPre记录上一位所有状态，程序结束时，记录的是最后一位的所有状态。m_vPre是二维向量，一维长度4，分别表示4种边界状态，下标0记录非上下界，下标1记录下界，下标2记录上界，3记录同时上下界。二维长度由构造函数的参数iResutlCount决定。ResultType类记录状态。ELE枚举的元素类型minEle元素最小值maxEle元

        本文章是对于完全背包一些题型(如题目所示，组合、排列和最小值类型)的总结和理解，依次记录一下，方便回顾与复习。    本文章是基于个人所总结实现的，但在其中遇到了一些疑惑与困难，所以总结一篇与完全背包相关的问题。    题型分为完全背包求组合问题、求排列问题、求最小值问题.但这一切都是基于完全背包，我们先来介绍一下什么是完全背包。目录完全背包问题二维dp 二维优化一维dp(滚动数组)完全背包组合和排列问题完全背包问题        有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，其价值为value[i]。每件物品都有无限个（也就是可以放入背包多次）

一、使用一维dp数组1.dp数组的定义：dp[j]表示背包最大容量为j时，所背的物品最大价值。2.递推公式：dp[j]=max(dp[j],dp[j-weight[i]]+value[i])3.遍历过程：对于每一个物品，都要从dp[bagweight]开始遍历到dp[weight[i]]。从后往前是为了防止一次遍历过程前面的物品放入多次。4.代码实现：for(inti=0;i=weight[i];j--){dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);}}二、背包问题的应用: 416.分隔等和子集1、题目描述给你一个 只包含正整数 的 非空 数组 nums