前言：动态规划的本质，是对问题状态的定义和状态转移方程。动态规划具备三个特点： 1.将原来的问题分解成几个相似的子问题; 2.所有的子问题都只需要解决一次 3.每个状态存储子问题的解一般从三个角度考虑动态规划： 1.状态表示: 2.状态计算- >集合的划分 3.状态初始化集合的划分依据，需要满足两个条件 1.以最后一个改变的元素为依据。 2.集合中应包含所有的方案。而动态规划问题一般可以分为线性DP，背包问题，区间DP，计数类DP，数位统计DP，状态压缩DP，树形DP，背包问题是大头，也是我们这章的重点。全文共12
前言：动态规划的本质，是对问题状态的定义和状态转移方程。动态规划具备三个特点： 1.将原来的问题分解成几个相似的子问题; 2.所有的子问题都只需要解决一次 3.每个状态存储子问题的解一般从三个角度考虑动态规划： 1.状态表示: 2.状态计算- >集合的划分 3.状态初始化集合的划分依据，需要满足两个条件 1.以最后一个改变的元素为依据。 2.集合中应包含所有的方案。而动态规划问题一般可以分为线性DP，背包问题，区间DP，计数类DP，数位统计DP，状态压缩DP，树形DP，背包问题是大头，也是我们这章的重点。全文共12
文章目录💬前言🎯week3🌲day10-1背包完全背包多重背包多重背包II分组背包🌲day2数字三角形-线性DP1015.摘花生-数字三角形🌲day3最长上升子序列-线性DP1017.怪盗基德的滑翔翼-LIS1014.登山-LIS最长公共子序列-线性DP🌲day4最短编辑距离-线性DP编辑距离-线性DP🌲day5石子合并-区间DP整数划分-计数DP🌲day6蒙德里安的梦想-状压DP最短Hamilton路径🌲day7没有上司的舞会-树形DP💬前言💡本文以经典DP入手，带你走进DP的大门，感受DP的魅力🔥🔥🔥DP是重中之重\blue{重中之重}重中之重，它能决定你的最终名次📌在比赛中DP是难点也是
文章目录💬前言🎯week3🌲day10-1背包完全背包多重背包多重背包II分组背包🌲day2数字三角形-线性DP1015.摘花生-数字三角形🌲day3最长上升子序列-线性DP1017.怪盗基德的滑翔翼-LIS1014.登山-LIS最长公共子序列-线性DP🌲day4最短编辑距离-线性DP编辑距离-线性DP🌲day5石子合并-区间DP整数划分-计数DP🌲day6蒙德里安的梦想-状压DP最短Hamilton路径🌲day7没有上司的舞会-树形DP💬前言💡本文以经典DP入手，带你走进DP的大门，感受DP的魅力🔥🔥🔥DP是重中之重\blue{重中之重}重中之重，它能决定你的最终名次📌在比赛中DP是难点也是
🌹作者:云小逸📝个人主页:云小逸的主页📝Github:云小逸的Github🤟motto:要敢于一个人默默的面对自己，强大自己才是核心。不要等到什么都没有了，才下定决心去做。种一颗树，最好的时间是十年前，其次就是现在！学会自己和解，与过去和解，努力爱自己。==希望春天来之前，我们一起面朝大海，春暖花开！==🤟👏专栏：C++👏👏专栏：Java语言👏👏专栏：Linux学习👏👏专栏：C语言初阶👏👏专栏：数据结构👏👏专栏：备战蓝桥杯👏文章目录前言完全背包问题问题定义二维解法二维状态定义：二维状态方程：以下是C++语言的实现代码：代码优化：一维解法一维状态定义：一维状态方程：以下是C++语言的实现代码：总
🌹作者:云小逸📝个人主页:云小逸的主页📝Github:云小逸的Github🤟motto:要敢于一个人默默的面对自己，强大自己才是核心。不要等到什么都没有了，才下定决心去做。种一颗树，最好的时间是十年前，其次就是现在！学会自己和解，与过去和解，努力爱自己。==希望春天来之前，我们一起面朝大海，春暖花开！==🤟👏专栏：C++👏👏专栏：Java语言👏👏专栏：Linux学习👏👏专栏：C语言初阶👏👏专栏：数据结构👏👏专栏：备战蓝桥杯👏文章目录前言完全背包问题问题定义二维解法二维状态定义：二维状态方程：以下是C++语言的实现代码：代码优化：一维解法一维状态定义：一维状态方程：以下是C++语言的实现代码：总
01背包问题商店的货架上摆放着不同重量和价值的商品，一个小偷在商店行窃，他携带的背包只能装固定重量的商品。装哪些商品才能获得最大的收益呢？在限定条件内找到最佳的物品组合，这样的问题统称为背包问题。根据限定的条件不同，背包问题还可以细分：部分背包问题：所有物品是可再分的，即允许将某件物品的一部分（例如1/3）放入背包；0-1背包问题：所有物品不可再分，要么整个装入背包，要么放弃，不允许出现“仅选择物品的1/3装入背包”的情况；完全背包问题：不对每一件物品的数量做限制，同一件物品可以选择多个装入背包；多重背包问题：每件物品的数量是有严格规定的，比如物品A有2件，物品B有3件。前面章节中，我们学会了
01背包问题商店的货架上摆放着不同重量和价值的商品，一个小偷在商店行窃，他携带的背包只能装固定重量的商品。装哪些商品才能获得最大的收益呢？在限定条件内找到最佳的物品组合，这样的问题统称为背包问题。根据限定的条件不同，背包问题还可以细分：部分背包问题：所有物品是可再分的，即允许将某件物品的一部分（例如1/3）放入背包；0-1背包问题：所有物品不可再分，要么整个装入背包，要么放弃，不允许出现“仅选择物品的1/3装入背包”的情况；完全背包问题：不对每一件物品的数量做限制，同一件物品可以选择多个装入背包；多重背包问题：每件物品的数量是有严格规定的，比如物品A有2件，物品B有3件。前面章节中，我们学会了
背包问题是动态规划非常重要的一类问题，它有很多变种，但题目万变不离其宗。我们需要抓住关键的解题思路，现将解题模板总结如下：背包问题的定义那么什么样的问题可以被称作为背包问题？换言之，我们拿到题目如何透过题目的不同包装形式看到里面背包问题的不变内核呢？我对背包问题定义的理解：给定一个背包容量target，再给定一个数组nums(物品)，能否按一定方式选取nums中的元素得到target注意：1、背包容量target和物品nums的类型可能是数，也可能是字符串2、target可能题目已经给出(显式)，也可能是需要我们从题目的信息中挖掘出来(非显式)(常见的非显式target比如sum/2等)3、选
背包问题是动态规划非常重要的一类问题，它有很多变种，但题目万变不离其宗。我们需要抓住关键的解题思路，现将解题模板总结如下：背包问题的定义那么什么样的问题可以被称作为背包问题？换言之，我们拿到题目如何透过题目的不同包装形式看到里面背包问题的不变内核呢？我对背包问题定义的理解：给定一个背包容量target，再给定一个数组nums(物品)，能否按一定方式选取nums中的元素得到target注意：1、背包容量target和物品nums的类型可能是数，也可能是字符串2、target可能题目已经给出(显式)，也可能是需要我们从题目的信息中挖掘出来(非显式)(常见的非显式target比如sum/2等)3、选
