动态规划-总结分析

❁声明：本文非完全原创性，其中参考资料摘自OI-WIKI：http://oi-wiki.com/dp/basic/，如有侵权，请联系我删除！ ※三创/转载请注明原始作者、原始文章地址及本博客地址 ☻文中如存在谬误、混淆等不足，欢迎批评指正！

动态规划应用于子问题重叠的情况：

1. 要去刻画最优解的结构特征；
2. 尝试递归地定义最优解的值（就是我们常说的考虑从 i − 1 i - 1 i−1 转移到 i i i ）；
3. 计算最优解；
4. 利用计算出的信息构造一个最优解。

动态规划的两种实现方法

1. 自顶向下法：记忆化搜索
2. 自底向上法(将问题按规模排序，类似于递推)

动态规划原理

动态规划要素：最优子结构、子问题重叠、重构最优解

最优子结构

具有最优子结构也可能是适合用贪心的方法求解。注意要确保我们考察了最优解中用到的所有子问题。

1. 证明问题最优解的第一个组成部分是做出一个选择；
2. 对于一个给定问题，在其可能的第一步选择中，你界定已经知道哪种选择才会得到最优解。你现在并不关心这种选择具体是如何得到的，只是假定已经知道了这种选择；
3. 给定可获得的最优解的选择后，确定这次选择会产生哪些子问题，以及如何最好地刻画子问题空间；
4. 证明作为构成原问题最优解的组成部分，每个子问题的解就是它本身的最优解。方法是反证法，考虑加入某个子问题的解不是其自身的最优解，那么就可以从原问题的解中用该子问题的最优解替换掉当前的非最优解，从而得到原问题的一个更优的解，从而与原问题最优解的假设矛盾。

要保持子问题空间尽量简单，只在必要时扩展。

最优子结构的不同体现在两个方面：

1. 原问题的最优解中涉及多少个子问题；
2. 确定最优解使用哪些子问题时，需要考察多少种选择。

子问题图中每个定点对应一个子问题，而需要考察的选择对应关联至子问题顶点的边。

经典问题：

• 无权最短路径： 具有最优子结构性质。
• 无权最长（简单）路径： 此问题不具有，是 NPC 的。区别在于，要保证子问题无关，即同一个原问题的一个子问题的解不影响另一个子问题的解。相关：求解一个子问题时用到了某些资源，导致这些资源在求解其他子问题时不可用。

子问题重叠

子问题空间要足够小，即问题的递归算法会反复地求解相同的子问题，而不是一直生成新的子问题。

重构最优解

存表记录最优分割的位置，就不用重新按照代价来重构。

闫氏DP分析法

总结自UP主：大雪菜(yxc)大佬(ACWing创始人)

核心思想：从集合的角度去分析DP问题

1.状态表示：用维度数组 d p [ i ] dp[i] dp[i]表示(维度根据题目来定)

• 集合： d p [ i ] [ j ] dp[i][j] dp[i][j]： d p dp dp数组的含义：确定状态下的 d p [ i ] [ j ] dp[i][j] dp[i][j],即满足约束条件下的解的集合，其值为属性的具体化

  通过寻找最后一个状态不同的点确定划分的方法

• 属性：集合内解的特性-最大值max、最小值min、集合元素的个数。

  注意： d p dp dp数组维护的是集合某种特性的值！

2.状态计算：即化整为零的过程。将大集合分成若干个子集，再通过子集地推出末状态

一般分析步骤：

1. 先根据题意确定dp数组的含义，再根据题目的诉求确定dp数组维护的特性
2. 分析出集合的划分方法（通过寻找最后一个状态不同的点确定划分的方法），得到递推方程
3. 确定初始化状态 d p [ 1 ] = ？ dp[1] = ？ dp[1]=？
4. 敲键盘

dp问题的下标

1. 若状态转移方程中有 f [ i − 1 ] f[i - 1] f[i−1]这种状态, 下标(状态转移那部分代码)尽量从1开始
2. 否则就最好从0开始

dp问题的时间复杂度 状态数量(n^几个约束维度) * 转移状态的时间复杂(状态转移代码的时间复杂度)

dp的集合划分依据 -> 寻找最后一个不同操作. 加不加这个背包, 数字三角形最后一步是由左边还是右边走过来的呀(根据操作的不同来对集合进行划分) 使得划分之后的小集合可以递推求出当前集合, 且最小集合已知

注意：集合的划分一定要不漏，不一定不重！

动态规划-分类 1.简单DP-序列处理问题 1.1.最长公共子序列

子序列允许不连续。每个 c [ i ] [ j ] c[i][j] c[i][j] 只依赖于 c [ i − 1 ] [ j ] c[i - 1][j] c[i−1][j] 、 c [ i ] [ j − 1 ] c[i][j - 1] c[i][j−1] 和 c [ i − 1 ] [ j − 1 ] c[i - 1][j - 1] c[i−1][j−1] 。

记录最优方案的时候可以不需要额外建表（优化空间），因为重新选择一遍（转移过程）也是 O ( 1 ) O(1) O(1) 的。

模板算法

ios::sync_with_stdio(false);
string a, b; cin >> a >> b;
int dp[MAX];
for(int i = 0; i  w[i] >> v[i];
    for(int i = 1; i  weight >> value >> numm;
        while(numm--) v[++flag] = value, w[flag] = weight;
    }
    for(int i = 1; i = w[i]; j--){
            dp[j] = max(dp[j - w[i]] + v[i], dp[j]);
        }
    }
    cout  m;
    //分组操作
    for(int i = 1; i > weight >> value >> num;
        while(num - c > 0){
            num -= c;
            w[++ind] = weight * c;
            v[ind] = value * c;
            c *= 2;
        }
        w[++ind] = weight * num;
        v[ind] = value * num;
    }
    //0-1背包模板
    for(int i = 1; i = w[i]; j--){
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    cout  m >> t;
    for(int i = 1; i > w1[i] >> w2[i] >> v[i];

    for(int i = 1; i = w1[i]; j--){
            for(int k = t; k >= w2[i]; k--){
                dp[j][k] = max(dp[j - w1[i]][k - w2[i]] + v[i], dp[j][k]);
            }
        }
    }
    cout  m;
    for (int i = 1; i > w[i] >> v[i] >> C;
        cn = max(cn, C); //cn记录共有几组
        cnt[C]++;         //cnt[]记录第C组共有几件物品
        t[C][cnt[C]] = i; //t[][]记录第C组第i件物品的的序号
    }
    for (int i = 1; i = 0; j--)         //枚举容量
            for (int k = 1; k = w[t[i][k]]) dp[j] = max(dp[j], dp[j - w[t[i][k]]] + v[t[i][k]]); //套用状态转移方程
    cout