最全动态规划题型详解

文章目录

• • 前言
  • 数字三角形模型
  • • • 1. 数字三角形
      • 2. 最低通行费
      • 3. 方格取数
      • 总结
      • 最长上升子序列模型
      • • • 1. 最长上升子序列（LIS）
          • 2. 怪盗基德的滑翔翼
          • 3. 最长公共子序列
          • 4. 最长公共上升子序列
          • 总结
          • 背包问题模型
          • • • 01背包
              • • 1. 01背包
                • 2. 装箱问题
                • 完全背包
                • • 1. 完全背包问题
                  • 2. 买书
                  • 多重背包Ⅰ
                  • 多重背包Ⅱ
                  • 分组背包
                  • 有依赖的背包问题
                  • 背包问题求方案数
                  • 总结
                  • 区间dp模型
                  • • • 1. 石子合并
                      • 2. 加分二叉树
                      • 总结
                      • 状态机模型
                      • • • 1. 大盗阿福
                          • 2. 股票买卖Ⅳ
                          • 3.股票买卖Ⅴ
                          • 总结
                          • 状态压缩dp
                          • • • 1.小国王（棋盘型状压dp）
                              • 2. 玉米田
                              • 总结
                              • 树形dp模型
                              • • • 1.没有上司的舞会
                                  • 2. 树的最长路径
                                  • 3. 树的中心
                                  • 4. 战略游戏
                                  • 总结
                                  • 数位dp模型
                                  • • • 1. 数的度量
                                      • 2. 数字游戏
                                      • 总结
                                      • 插头dp模型
                                      • dp的优化方法

                                        前言

                                        ---

                                        由于动态规划没有固定的套路并且个人认为也是算法里面最难的算法，所以这里讲解动态规划常见的几种模型，因为本文是自己学习后的总结，所以后面还会补充一些细节。

                                        如有错误请及时指出

                                        ---

                                        什么是动态规划（官方解释，但好像没什么用）

                                        动态规划 Dynamic Programming，DP：是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。

                                        动态规划的核心思想

                                        通俗的讲dp的核心就是记住已经解决过子问题的解，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。dp常常适用于有重叠子问题和最优子结构性质的问题,动态规划方法所消耗的时间往往远小于朴素解法。

                                        分治和动态规划的区别

                                        共同点：两者都要求原问题具有最优子结构性质，都是将原问题分而治之，分解成若干个规模较小的子问题，然后将子问题的解合并，最终得到答案。

                                        不同点：分治法将分解后的子问题看成相互独立的，通常用递归来做。动态规划将分解后的子问题理解为相互间有联系，有重叠部分，需要记忆，通常用迭代来做。

                                        动态规划性质

                                        1. 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理
                                        2. 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
                                        3. 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）

                                        动态规划的步骤

                                        1. 确定dp数组及其下标的含义；（找出状态表示）
                                        2. 确定递推公式；（确定状态转移）
                                        3. dp数组如何初始化；
                                        4. 确定遍历顺序；
                                        5. 举例推导dp数组。

                                        求状态表示的小技巧：

                                        一般由题目要求什么，状态表示就表示成什么。

                                        求状态转移的小技巧：

                                        可将所有物品（比如：背包问题中题目给出的物品就是‘物品’，子序列问题中每个数就是物品，股票问题中股票就是物品）看成一个集合，这个集合又是由几个集合组成，然后可以考虑某一个状态表示是由哪几个集合转移来的（前面的集合已经求出）。 举个例子：在背包问题中，可以将所有物品看成一个集合，那么这个集合可能由不同的集合组成，也就是不同的物品组合，然后在目前这个背包容量下可以是由前面哪个集合转移过来才能使价值最大（将哪个物品组装入才能使价值在不超过容量的前提下价值最大）。要是看不懂可以将后面背包问题看了在回来看这儿

                                        哪种题型一般使用动态规划求解

                                        1. 最优解问题：数组中最大值型，比如：最长上升子序列，最大子数组，最长公共子序列等问题。
                                        2. 求可行性问题：如果有这样一个问题，让你判断是否存在一条总和为 x 的路径（如果找到了，就是 True；如果找不到，自然就是 False），或者让你判断能否找到一条符合某种条件的路径，那么这类问题都可以归纳为求可行性问题，并且可以使用动态规划来解。
                                        3. 求方案数问题：求方案总数也是比较常见的一类动态规划问题。比如说给定一个数据结构和限定条件，让你计算出一个方案的所有可能的路径，那么这种问题就属于求方案总数的问题。

                                        数字三角形模型

                                             ~~~~     

                                        1. 数字三角形

                                        解题思路

                                        可将题目中所有元素看成一个集合，题目中要求路径中的数字和最大，并且题目中的元素的二维排列的，那么状态表示就可以是f[i][j]表示沿着某条路径走到第i行第j列这条路径上的数字和为多少，那状态转移怎么算呢？就像我们上面说的，我们可以看第i行第j列这个状态可能由哪些集合转移过来，可以看到第i行第j列可以由第i-1行第j列和第i-1行第j-1列转移而来，而第i-1行第j列和第i-1行第j-1列这两个状态可以表示成f[i-1][j],f[i-1][j-1]（也就是上面提到的集合），虽然f[i][j]可以由f[i-1][j-1]表示，但是前提是这两个状态（也可以说成这两个集合）得求出来。

                                        状态表示：f[i][j]表示从左上角走到第i行第j列的和的最大值

                                        转移方程：f[i][j] = max(f[i-1][j-1],f[i-1][j])

                                        此模型也可转换为最长路径问题

                                        代码如下

                                        #includeusing namespace std;const int N = 510,INF = 0x3f3f3f3f;int a[N][N],f[N][N];int main(){int n;cin>>n;for(int i=1;ia[i][j];//先将f数组初始化for(int i=0;i    cinn;    for(int i=1;i    cinn;    int a,b,c;    while(cinabc,a||b||c) g[a][b]=c;    for(int k=1;k        for(int i1=1;i1            for(int i2=1;i2                int j1=k-i1,j2=k-i2;                if(j1=1&&j1                    int t=g[i1][j1];                    if(i2!=i1) t+=g[i2][j2];                     int &x = dp[k][i1][i2];                    x = max(x,dp[k-1][i1-1][i2-1]+t);                    x = max(x,dp[k-1][i1-1][i2]+t);                    x = max(x,dp[k-1][i1][i2-1]+t);                    x = max(x,dp[k-1][i1][i2]+t);                }            }        }    }    coutint n;cinn;for(int i=1;ifor(int j=1;jif(a[i]a[j]) f[i] = max(f[j]+1,f[i]);}res = max(res,f[i]);}cout    cink;    while(k--)    {        int n,res=0;        cinn;        for(int i=1;i            dp[i] = 1;            for(int j=1;j            dp[i]=1;            for(int j=n;ji;j--)                if(g[i]g[j])                    dp[i] = max(dp[i],dp[j]+1);            res = max(res,dp[i]);        }                cout    cinnm;    cina+1b+1;    for(int i=1;i        //如果a[i]!=b[j]            f[i][j]=max(f[i][j-1],f[i-1][j]);            //如果a[i]==b[j],那就是i-1,j-1结尾的最长公共子序列+1            if(a[i]==b[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1);        }    cout    cin  n;    for (int i = 1; i         int maxv = 1;        for (int j = 1; j             f[i][j] = f[i - 1][j];            if (a[i] == b[j]) f[i][j] = max(f[i][j], maxv);            if (a[i]  b[j]) maxv = max(maxv, f[i - 1][j] + 1);        }    }    int ans = 0;    for (int i = 1; i int n,m;cinnm;//n件物品和体积限制for(int i=1;icinvn;for(int i=1;i f[i][j] = f[i-1][j];if(j-v[i]=0) f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);} f[i][j] = f[i-1][j];if(j-v[i]=0) f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);}         f[j] = max(f[j],f[j-v[i]]+w[i]);}    int n,m;    cinnm;    for(int i = 1 ; i         cinv[i]w[i];    }    for(int i = 1 ; i            f[j] = max(f[j],f[j-v[i]]+w[i]);    }    cout10,20,50,100};//f[N]表示钱数为n时的方案数//f[j] = f[j-a[i]]+f[j];第i个物品选不选int f[N],n;int main(){cinn;f[0] = 1;for(int i=0;ifor(int j=a[i];jint n,m;cinnm;for(int i=1;i//最后枚举第i种物品的个数for(int k=0;k*v[i]    int n,m;    int cnt=0;    cinnm;    for(int i=1;i        int a,b,s;        cinabs;        int k=1;        while(k            cnt++;            v[cnt]=a*k;            w[cnt]=b*k;            s-=k;            k*=2;        }        if(s0)        {            cnt++;            w[cnt]=b*s;            v[cnt]=a*s;        }    }    n=cnt;    for(int i=1;i    int n,m;    cinnm;    for(int i=1;i        cins[i];        for(int j=0;j>w[i][j];    }        //枚举物品组    for(int i=1;i=0;j--)        //枚举决策，也就是选这个物品组的哪个物品            for(int k=0;k    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;}void dfs(int u){//其实是一个分组背包问题    //先枚举所有状态体积小于等于j-v[u]的所有子节点们能够获得的最大价值    for (int i = h[u]; ~i; i = ne[i])    {    //先取出子节点        int son = e[i];        dfs(son); //从下往上算，先计算子节点的状态        for (int j = m - v[u]; j = 0; -- j) //枚举所有要被更新的状态        {            for (int k = 0; k                 f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);            }        }    }    //选上第u件物品    for (int j = m; j = v[u]; -- j) f[u][j] = f[u][j - v[u]] + w[u];    for (int j = 0; j > w[i] >> p;        if (p == -1) root = i;        else add(p, i);    }    //不管选择哪个物品都会在选择根结点，所以找出根节点从根节点开始dfs    dfs(root);    cout     cinn>>m;    for(int i=1;i>v[i]>>w[i];    for(int i=n;i>=1;i--)        for(int j=0;j            f[i][j]=f[i+1][j];            if(j=v[i]) f[i][j] = max(f[i][j],f[i+1][j-v[i]]+w[i]);        }            int j=m;    for(int i=1;i=v[i]&&f[i][j]==f[i+1][j-v[i]]+w[i])        {            coutint n;cinn;for(int i=1;ifor(int i=1;i+len-1int l=i,r = len+i-1;f[l][r] = 1e9;for(int k=l,k         // 区间长度  for (int i = 1; i + len - 1  // 枚举起点    int j = i + len - 1;                 // 区间终点    if (len == 1) {    dp[i][j] = 初始值    continue;}for (int k = i; k