第一节课总结

动态规划可主要分为二步，第一步是状态表示 状态表示又可分为 集合的形式（比如f【n】【m】存的是从f【1】【1】到f【n】【m】路径的所有集合） 和 集合的属性（max min bool 数量 等）
第二部是 状态的计算 状态的计算通常是以最后一步的不同之处来划分状态的 这里讲究要不重 和 不漏 但并不是要两个条件都符合，需要看情况讨论 ，比如在求max的时候不重这个条件可以不满足，对最后的结果是没有影响的；
动态规划模板例题：
摘花生；
最低通行费；
这两题都是路径的集合，但是在最低通行费里求min的时候得特别注意边界问题，比如在第一行的时候必须特判不能从上走下来，和第一列是同理的，要不然会影响min值,特别是f【1】【1】这个位置的特判特别重要，这样的话应该就行了；
还有一题有点小难；
方格取数；
这题的动态规划状态表示为f[i1][j1][i2][j2],但会发现当都走到同一个方格的时候这个方格不能被重复计算两次，而且只有步数一样的时候才会走到同一个方格，所以可以巧妙的表示为f[k][i1][i2],k为i1+j1或者i2+j2的总步数，j1是纵坐标通过总步数k-i1可计算出来;

第二节课总结
这节课重点为求最长单调递增子序列的最大数量
算法基础课的模板题
最长上升子序列1 这种求最大上升子序列问题集合的角度是如何来区分的？ 是以f[i-1]来表示的 也就是以a[i-1]结尾的所有子序列的集合在其中求max，为什么要以a[i]的前一个数结尾呢，应为这样才能知道a[i]到底能不能接上来；
怪盗基德的滑翔翼
还有nlongn贪心 优化的最长上升子序列2 ；

登山 害 语文不好我题没读懂不知道求啥
合唱队形 求的东西和登山求的一样的东西
最大上升子序列和 这个无非就是把 最长上升子序列1 改来求和 不同的是最后还要多一步遍历f[i]求最值 哦想起来了，像这种求最大上升子序列问题一般最后一步都要遍历f[]数组来求最值，因为其中有一些状态有些序列是不满足条件的，比如a[j]>a[i]，这种的话就不用计算和第一节课讲的有一点不同，那个可以直接输出f[n][m]即可，这要特别注意一下
友好城市 我觉得应该是这节课最难的吧 得对其结构体进行排序，转换成一个最大上升子序列问题求解

第三节课总结
本节课的重点也是线性dp，先来个算法基础课的模板题引入
最长公共子序列 集合是以f[i][j]来划分的，状态表示具体可分为4种状态，包含a[i]不包含b[i]，都包含，都不包含，还有一个和第一个反着的， i为序列1的结尾元素，在这f[i-1][j]着表示的是一定不包含a[i]但是b[j]却是可能包含b[j] 和 不包含b[j] 这就体现了求最大值可以重复的性质，都包含的情况不一定一定存在，需要当a[i]==b[j]时候才可以，可写成 f[i][j]=max(f[i-1][j-1]+1,f[i][j]); 而都不包含的情况会包含到第二种和第三种的情况里，所以可以去重，不用计算；

第四节课总结
先复习一下背包基础模板问题
01背包问题 ；状态表示为f[i][j] i表示在前几个物品中选，并且选的体积为不超过j的总价值；如果选j物品的话，需要此时的j>=w[i];
完全背包问题 ；这个是物品可以无限选，可以推个公式优化得
f[i][j-w] 和 f[i][j] 只相差后者空间大w，可以多个同一个物品的价值； 2相当于求前缀和最大值
多重背包问题 I 相当于求滑动窗口的最大值 这个是每个物品数量有限，可用3for循环枚举算出答案，因为本题数据范围较小，下一道题就得用线性优化；
多重背包问题 II；
分组背包问题 ；
男人八题也先放一下吧 受不了了
_上面的问题都可以优化，但是我太笨了，先放一下吧_等我把简单的先做了 再回来收拾难题
采药 装箱问题
宠物小精灵之收服这道题的话是二维费用流背包问题与完全背包结合的问题，f[i,j,k]表示的是在前i个物品中选，且费用1不超过j，费用二不超过k的选法 性质就是count精灵的数量，直接f[i,j,k]+1就行，这的i用做循环次数控制；j，k用作控制f数组下标；

第五节课总结

主题 二维费用的背包问题
二维费用的背包问题 因为是二维费用，多了一种费用，所以得多一维来表示，集合是 f[i,j,k]来表示的，是前i件物品中选，并且费用1不超过j和费用2不超过k所有合理选法里的最大值，属性也就是max；
我没优化写出来是3维的，但可优化成2维的，但不会 ，我现在回头去学；
上一节课总结了一句体积是从大到小循环还是从小到大的循环：
也就是如果状态计算的时候，用的是上一层的状态，就得从大到小枚举体积，
如果用的是本层的状态，那就从小到大枚举体积；
当空间优化成1维的时候，只有完全背包问题的体积是从小开始循环的，其余的背包问题都是从大到小循环的，如果没有优化的话，那么想怎么循环就怎么循环，没有任何限制 在优化完空间之后第一个是for物品第二个是for体积第三个是for决策

卧槽，nb啊，
我悟了 先来看01背包优化，01背包能优化的根本原因是当计算f[i][j]时只会用到上一成的值f[i-1][j-x]+价值，这根本不需要记录过程值，只需要用滚动数值去一直覆盖上一个值就行，还有一个原因就是在计算结果的时候无论用到的是f[i][j]还是f[i][j-v]都是严格小于v的，这个状态会在v的左侧被计算，而不会出现在v的右侧或者两边，所以也可以优化掉一维，只不过这有个细节就是在计算f[i][j]时用到的f[i][j-x]一定会在此之前被计算更新，就会导致这个不是上一层的状态，而是这一成的状态，所以我们可以倒着计算，从最大体积开始循环，这样就可以了~牛逼简简单单
接下来解决完全背包优化完全背包问题可以优化到两维 啊这 这个之前会的，就是找到一个关系，当这个背包体积大于同一层状态 也就是能比前一个多装一个，那就不用每次都 for枚举了，直接又上一个推出即可 f[i][2v]=f[i][v]+w;注意这的i没有-1，因为是同一层状态；
接下来解决多重背包问题1，这个的话可以直接3for暴力解决；
多重背包问题11就是它的优化版，3for肯定跑不过；这要用二进制优化,具体做法是把每一个物品的数量用二进制来拆分，把这些拆分下来的数量存入数组，从而转换成一个01背包问题，通过选与不选，可以完美的把这个数量从0枚举到这个数，比如1024，利用二进制拆分转换成01背包问题，从0（n）转化成lg（n）；
分组背包问题~~~也是可以转化成一维的，牛逼
以上都是基础知识 草~第五节课还没看明天看吧，摆烂！

背包模型（二）
课堂总结；
二维费用背包问题01背包结合：从前i个物品中选，通常且来说费用1不超过j，费用2不超过k，也不是一定，比如可以是取这么多，两个费用恰好相等；
二维费用的背包问题 之前直接写的3维的，也能过，但可以优化乘2维的，

潜水员，是和01背包结合的一道问题，但是状态表示也和之前的有一点不同，就是这的状态表示是前i个物品中选，也就是上面刚说的费用1恰好等于j，费用2恰好等于k，的所有选法集合，这得注意初始化，因为有些状态是不合法的，比如选0个的时候，但是费用1 和 费用2 却不能等于i/j ,还有费用1和费用2 体积的时候得下标减一，之前没注意，，这得注意下=一下，要不然要越界；状态计算
f[j][k]=min(f[j][k],f[max(0,j-O[i])][max(0,k-N[i])]+W[i])，因为下标为负的时候那就不合理，直接取f[0][0]相当于不选，那为什么之前没有这个min判断条件，那是应为循环条件里会限制大于此时的条件1和2，那为什么这个不能直接那样写，因为那个状态表示和这个不一样，那个是前i个物品里选不超过条件1和条件2的方案选法的集合，而这个是恰好等于条件1和条件2的选法的集合，也就意味着那个就算一个不选f[i>0][j>0]也合法，而这个却不行，因为这个要是一个不选的话，是不能等于条件1和2的，所以是不合理的，那么就要用f[0][0] 来过渡，因为其他的f[i][j]初始话为0x3f3f3f3f,，其他的会影响最终结果的；

[数字组合](https://www.acwing.com/problem/content/280/) 
这道题的状态标示也是从前i个物品中选，体积恰好等于j的所有选法的集合
状态计算是分为两种情况，选a[i]和不选a[i] 则将这两种方案一起加起来
但这道题和上一道题把我搞模糊了，就是在求状态计算的时候，那个for循环的条件，到底是大于等于j的
还是大于等于0啊
玩了一天后，看了帅气可爱阳光学长写的题解，终于悟了，就是上一个问题（二维费用的背包问题），在for为什么不能写成循环到0，因为那样的话，方案就不合理了，比如当背包容量只有10的时候你却让其装下20的东西，那显然是不合理的，所以可以直接写成大于等于条件1、2的方案，而这个问题（潜水员），为啥子for条件要写到0，因为这是求最小值问题，你可以细想一下，当氧气和氮气的量都满足后，有很多种方案，而在这方案中，氧气和氮气体积都是不一样的，对于最后的答案，我们需要在这些>=给出的条件中，找一个最小值就可以了，那最大值到底该枚举到哪里，先放一下，等会回来看；
 [庆功会](https://www.acwing.com/problem/content/1021/) 我用的3for1维过的，可以用单调队列和二进制优化；
  [买书](https://www.acwing.com/problem/content/1025/) ；我当时想的是状态表示为在前i个中选，且体积等于j的所有选法的集合，自然而来其他的 f[i]==1,其他的都==0，性质嘛就是count，那么状态计算是什么，以最后一步不同之处来看，计算f[i]的时候就是有两种方案，选a[i]的和不选a[i]的，将两种相加就可以了；  
  这也可以优化成2for，加个if就可以了，由本成的状态可以推出来

背包问题3
背包问题求具体方案
思路就是先看作一道01背包问题选方案，不同之处就是让你输出选的方案是由哪些物品构成的，
先做一遍01背包，但这要倒的做，从第n个物品开始选，这样的话到时候可以直接正着推这个状态是由哪个状态转移过来的，也就是判断(f[i][v]==f[i+1][v-vv[i]]+ww[i]&&v>=vv[i]) ，如果为真，则能选必选，不能选则必不选，将此时状态更新，输出方案序号就行；

机器分配 这题可分为两部分，前一部分就是求最大值max，可以看作分组背包，每个组只能选一种情况，而这个分组背包里又分为几种情况，比如选0台机器，1太机器，2太机器等，而这个台数可以当作体积来限制；后部分就是倒着推方案，从后往前推，但得到的方案的反转一下，这最后输出得注意一下，不能特判台数为0就不输出，其实台数是0也是一种方案，也得输出；
开心的金明 简单的01背包
金明的预算方案 2h.10有点东西，先放一下，有点难

背包问题4
货币系统； 和买书那题一样的，注意一下当f[i] 的 i小于a[i]的时候不能算
货币系统升级版 核心思路和上题的差不多，就是判断一个数a[i]能不能a[i]前面的数拼凑出来，如果可以的话，那么这个数就是无用的，就可以将其舍弃，如果不能拼凑，那么这个数必选，那么如何判断呢，可以弄个for循环，直接判断f[i]是否为0，如果是的话，则拼不出来，答案++，每次再从这个数 状态计算 一直算到最后那个数，计算这些算能被前面的数拼出多少次；
混合背包问题

先这样吧，等再学一点再过来重新总结！