那些正常的动态规划

目录

• 媒介
  
  
  
  • 动态规划到底是啥？
    
  
  
• 线性dp
  
  
  
  • 最长上升子序列
    
    
    
    • 子集和子序列和子串的区别
      
    • 内容分析
      
    
    
  • 最大上升子序列
    
  • 例题1——[NOIP2004 提高组] 合唱队形
    
    
    
    • 分析
      
    
    
  • 最长公共子序列
    
  • 最长公共子串
    
  
  
• 平面dp
  
  
  
  • 例题2——[NOIP2000 提高组] 方格取数
    
    
    
    • 分析
      
    
    
  • 例题3——[NOIP2008 提高组] 传纸条
    
    
    
    • 分析
      
    
    
  • 例题4——最大加权矩形
    
    
    
    • 分析
      
      
      
      • 增补：最大字段和
        
      • 最大子矩阵和和最大字段和的关联
        
      
      
    
    
  • 例题5——最大全1子矩阵
    
    
    
    • 分析
      
    
    
  • 例题6——穿衣服
    
    
    
    • 分析
      
    
    
  
  
• 背包问题
  
  
  
  • 什么是背包问题
    
  • 背包的分类
    
  • 01背包
    
    
    
    • 思路一
      
    • 思路二
      
    • 思路三（重头戏）
      
      
      
      • 常规代码
        
      • 空间优化
        
      
      
    
    
  • 例题7——[NOIP2001 普及组] 装箱问题
    
    
    
    • 分析
      
    
    
  • 例题8——最约莫数和
    
    
    
    • 分析
      
    
    
  • 多重背包
    
    
    
    • 
      
      
      
      • 位置1
        
      • 位置2
        
      
      
    • 二进制优化
      
    • 完整代码
      
    
    
  • 例题9——[NOIP1996 提高组] 砝码称重
    
    
    
    • 分析
      
    
    
  • 完全背包
    
    
    
    • 优化
      
      
      
      • 优化办法一
        
      • 优化办法二（重点）（敲黑板）
        
      
      
    
    
  • 例题10——疯狂的采药
    
    
    
    • 分析
      
    
    
  • 混合背包
    
  • 多维背包
    
  • 例题11——「一本通入门 2.9.2」 潜水员
    
    
    
    • 分析
      
    
    
  • 分组背包
    
  • 例题12——旅行者
    
    
    
    • 分析
      
    
    
  • 泛化背包
    
  • 例题13——精力的分配
    
    
    
    • 分析
      
    
    
  • 有依赖的背包
    
  • 例题14——[NOIP2006 提高组] 金明的预算方案
    
    
    
    • 分析
      
    
    
  • 背包方案数
    
  • 例题15——方案数
    
    
    
    • 分析
      
    
    
  • 01背包问题输出方案
    
  • 背包问题总结
    
  
  
• 区间dp
  
  
  
  • 区间型动态规划的特点：
    
  • 例题16——一本通改编——衣服合并
    
    
    
    • 分析
      
    
    
  • 小结1
    
  • 例题17——1275：【例9.19】乘积最大
    
    
    
    • 分析
      
    
    
  • 小结2
    
  • 例题18——[IOI2000] 回文字串
    
    
    
    • 分析
      
    
    
  • 环形区间dp
    
  • 例题19——[NOI1995] 石子合并
    
    
    
    • 分析
      
    
    
  • 例题20——[NOIP2006 提高组] 能量项链
    
    
    
    • 分析
      
    
    
  • 例题21——[NOIP2001 提高组] 数的分别
    
    
    
    • 分析
      
    
    
  • 例题22——放苹果
    
    
    
    • 分析
      
    
    
  
  

媒介

在说线性dp之前，我们先来聊一聊动态规划是啥？
动态规划到底是啥？

动态规划是普及组内容中最难的一个部分，也是每年几乎必考的内容。它对思维的要求极高，它和图论、数据结构不同的地方在于它没有一个标准的数学表达式和明白清晰的解题方法。
动态规划是对求解最优解的一种途径，而不是一种特殊的算法。由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的阶梯方法，而不存在一种万能的动态规划算法。为了方便学习，我们把若干具有代表性的动态规划问题归纳总结成不同的几类，并建立对应的数学模型。
动态规划一般用来求解多阶段决策问题的最优解，可以将过程分成若干个相互联系的阶段，在它的每一阶段都需要做决策，从而使整个过程到达最好的活动结果。各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线。

对于动态规划问题，最紧张的是分析出：
一、决策对象：我们需要对题目中的哪个变量举行决策。
二、阶段：需要将问题的全过程恰当的分成若干个相互联系的阶段，以便按肯定的序次去求解。阶段的分别一般是根据时间(先后顺序) 和 空间(大小关系) 的天然特征来分别。
三、状态：某一阶段的出发位置称为状态，一个阶段可能包含多个状态，状态大多都是用 数组 来表示，即表示我们需要的答案。
四、决策：分析完问题后我们应该怎么解决问题。
五、状态转移方程：形貌前一阶段到后一阶段的状态演变规律。
线性dp

线性动态规划是动态规划中比较简朴的一类问题，他的状态转移是线性的，即状态的转移是固定的，常见的如从前到后，或者从后到前。线性动态规划和递推比较类似，在很多情况下，这两种做法大致是相同的。一般的，递推是当前要求解的答案和前面某个固定答案有关，而线性动态规划是当前答案和前面的某个答案存在关系，这个位置在不同的情况下是不相同的。
最长上升子序列

言归正传，我们继承聊线性dp。
子集和子序列和子串的区别

以\(abfsgegsas\)为例，\(faggas\)是它的子集，由于子集是不计顺序的，\(abggss\) 则是他的子序列，由于子序列是要求有顺序的，而\(abf\)则是他的字串
内容分析

决策对象
每个位置上的数。
阶段
共有 \(n\) 个数，因此有 \(n\) 个阶段。
状态
由于每个数都有可能是子序列的结尾，所以利用 dp 表示以第 \(i\) 个数作为结尾的最长上升子序列的长度。
决策
如果以第 \(i\) 个数作为结尾，那么在这个序列中，上一个数肯定要小于 \(a\)。因此，我们需要在前面的数中找到比 \(a\) 小的数，而且我们应该选择以这个数结尾的最长上升子序列中最长的那个，这样接在这个数后面得到的序列也是最长的。

状态转移方程
如果 \(h[k]>n;        for (int i=1;i>a;                dp=1;        }                for (int i=1;ib;    dp[0][0]=0;    for (int i=1;ib;        dp[0][0]=0;        for (int i=1;i>n;        while (1){                int a,b,c;                cin>>a>>b>>c;                if (a==0&&b==0&&c==0)break;                mp[a]=c;        }        for (int i=1;ib>>c;                if (a==0&&b==0&&c==0)break;                mp[a]=c;        }        for (int i=1;i