动态规划

====

动态规划难点

  • 意识到这个题用动态规划解决
  • 高效设计状态
  • 多做题

最长上升子序列问题

  • 题目: ()
  • 设计状态:
  • $f\[i\]$表示以$a\[i\]$结尾的最长上升子序列长度。
  • 最终答案$max_1\\leq i \\leq n$
  • 如何转移?

    for(int i=1;i<=n;i++){
    f[i]=1;
    for(int j=1;j<i;j++){
    if(a[i]<a[j]) f[i]=max(f[i],1+f[j]);
    }
    }

  • 时间复杂度$O(n^2)$
  • 如何优化?

方法一:树状数组优化

  • 假设$a_i$互不相同。
  • 离散化:$a\_1,a\_2,...,a_n$是一个${1,2,...,n}$的排列
  • DP值$f\[i\]$插入数组的$a_i$位置(这里树状数组用于求前缀max)
  • 离散化?

    //a[i]互不相同时
    int a[N];
    int a2[N];
    int ord[N];
    int cmp(int i,int j){
    return a[i]<a[j];
    }
    void lsh(){
    for(int i=0;i<=n;i++){
    ord[i]=i;
    }
    sort(ord+1,ord+n+1,cmp);
    for(int i=1;i<=n;i++){
    a2[ord[i]]=a[i];
    }
    }

  • 时间复杂度$O(nlogn)$。

方法二:"单调栈"

  • 令$g\[j\]$表示目前为止,长度为j的上升子序列的末尾元素最小是多少。
  • $a\[1...5\]={1,5,2,4,3}$ $g\[1\]=inf$ 插入1,$g\[1\]=1,g\[2\]=inf$ 插入5,$g\[1\]=1,g\[2\]=5,g\[3\]=inf$ 插入2,$g\[1\]=1,g\[2\]=2,g\[3\]=inf$ 插入4,$g\[1\]=1,g\[2\]=2,g\[3\]=4,g\[4\]=inf$ 插入3,$g\[1\]=1,g\[2\]=2,g\[3\]=3,g\[4\]=inf$
  • 如何快速更新?
  • 二分查找?
  • 时间复杂度$O(nlogn)$
  • 假如输入数列有重复? 映射到不同的值上。

例题

  • 输入一个整数序列$a\_1,a\_2,...,a_n$,最少需要修改几次使整个序列变成严格上升序列?(要求修改后均为整数)。
  • 让$a_i$减去$i$,得到一个数列,求n-该数列最长不下降子序列长度。

最长公共子序列

  • 状态:$f\[i\]\[j\]$表示$s\[1..i\],t\[1,,j\]$的最长公共子序列
  • 转移方程: $s\[i\]=t\[j\]:f\[i\]\[j\]=f\[i-1\]\[j-1\]+1$ $s\[i\]\\neq t\[j\]:f\[i\]\[j\]=max{f\[i-1\]\[j\],f\[i\]\[j-1\]}$
  • 时间复杂度$O(n^2)$
如果$s,t\\leq100000$呢?
  • 保证s中每一个元素出现的次数小于10次。
思路
  • 如果互不相同
  • 让t中在s中没有出现过的元素删去,让t以s的顺序排序,算一个最长上升子序列。
  • 那次数$\\leq10$呢?
  • 转化为LIS(最长上升子序列)
  • 例如: s=abdbad t=abcbd a:5,1 b:4,2 c:。。 d:6,3 所以t转化为5,1,4,2,4,2,6,3 再求t的最长上升子序列。
  • 总结起来就是: 将每个元素在s中出现的下表以降序存在一个链表里,未完。。。

DAG上的dp

  • 输入一个有向无环图(DAG),并给定起点s,边权为正,计算从s到每个点u的最长路长度$d\[u\]$.
  • 要求时间复杂度$O(n+m)$
  • 先进行拓扑排序$v\_1,v\_2...,v\_n$ 假设$v\_1=s$。(否则,s走不到排在s前面的点,可以直接设置它们最短路为-inf)
  • $d\[v\_i\]=0$ 从$i=2,...,n$,枚举所有指向$v\_i$的边,计算的$d\[v\_i\]=max{d\[v\_j\]+w(v\_j,v\_i)}$

记忆化搜索

记忆化搜索

背包问题

01背包

  • 有$n$个物品,每个有体积$w\[i\]$,价值$v\[i\]$。总体积为$W$的背包最多能装多少总价值?
  • $(n,W\\leq2000)$
  • 设计状态:$f\[i\]\[j\]$表示$j$体积装前$i$件物品,最大的总价值。
  • 如何转移? $f\[i\]\[j\]=max(f\[i-1\]\[j\],f\[i-1\]\[j-w\[i\]\]+v\[i\])$ cpp for(int i=1;i<=n;i++){ for(int j=0;j<=w[i];j++) f[i][j]=f[i-1][j]; for(int j=w[i];j<=W;j++){ f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]) } } 优化空间后:

    for(int i=1;i<=n;i++){
        for(int j=W;j>=w[i];j--){
            f[j]=max(f[j],f[j-w[i]]+v[i])
        }
    }

完全背包

  • 有$n$种物品,每种有体积$w\[i\]$,价值$v\[i\]$且有无限个。总体积为$W$的背包最多能装多少总价值?
  • $(n,W\\leq2000)$ cpp for(int i=1;i<=n;i++){ for(int j=w[i];j<=W;j++){ f[j]=max(f[j],f[j-w[i]]+v[i]) } }

子集和问题

  • 有$n$个物品,第$i$个体积为$w_i$。能否选出一个子集和,使总容量为$W$的背包装满?
  • $f\[i\]\[j\]=1 or 0$表示用前$i$件物品能否凑出$j$体积。
  • $f\[0\]\[0\]=1$ cpp for(int i=1;i<=n;i++){ for(int j=0;j<=W;j++) f[i][j]=f[i-1][j]; for(int j=w[i];j<=W;j++){ if(f[i-1][j-w[i]]) f[i][j]=1; } } //f[n][W]==1 or 0?

动态子集和问题

动态子集和问题

01背包

  • 有$n$个物品,每个有体积$w\[i\]$,价值$v\[i\]$。总体积为$W$的背包最多能装多少总价值?
  • $(n\\leq2000,v\[1\]+v\[2\]+···+v\[n\]\\leq2000,W\\leq10^9)$
  • 小技巧:反转状态和dp值 状态$f\[i\]\[v\]$表示前$i$件物品凑出$v$的总价值最小总体积。 边界$f\[0\]\[0\]=0$。
  • 伪代码:

    f[0][0]=0;
    for(int i=0;i<=n;i++){
    f[0][i]=inf;
    }

    for(int i=1;i<=n;i++){
    for(int j=0;j<=2000;j++){
    f[i][j]=f[i-1][j];
    }
    for(int j=0;j<=2000;j++){
    f[i][j]=min(f[i][j],f[i-1][j-v[i]]+w[i]);
    }
    }

区间DP

合法子序列问题

  • 一个由$$组成的序列,求出最长的合法子序列长度,$(n\\leq300)$。
  • 定义:合法子序列是一个合法的括号序列,每一对匹配的括号都是同一类型的。比如$[()\[\]](()())$是合法的。
  • 设计状态: $f\[i\]\[j\]$表示在$\[i,j\]$有多长的合法子序列。
  • 转移: 如果$a\[l\],a\[r\]$是匹配的括号,则$2+f\[l+1\]\[r-1\]$ 枚举断点$k:f\[l\]\[k\]+f\[k+1\]\[r\]$
  • 按什么顺序进行DP? 区间长度从小到大的顺序。 (或者:记忆化搜索)
  • 时间复杂度:$O(n^3)$

矩阵链乘法

  • 将一个$p \\times q$的矩阵乘一个$q \\times r$的矩阵,得到一个$p \\times r$的矩阵,运算花费是$p \\times q \\times r$。
  • 现在输入$p\_1,p\_2,p\_3,...,p\_n$。将$p\_1 \\times p\_2,p\_2 \\times p\_3,...,p_{n-1} \\times p_n$的矩阵乘起来,最小的总运算花费是多少?

例题n(记不清了)

例题 - 设计状态: $f\[l\]\[r\]$表示$a\[l,r\]$字串的答案。 - 转移:$f\[l\]\[k\]+f\[k+1\]\[r\]$ 当a[l]==a[r]时,未完。。。

Floyd也是dp

  • n个点的无向图,有向点和边权。每一对s,t,计算从s到t的路径,使得最小化:路径上的总边权+路径最大点权
  • $(n\\leq300)$

状态压缩DP

经典问题

  • 求n个点的无向图的色数。(可以把顶点染成k种颜色之一,使得每条边两端不同色。最小的k是多少)
  • $n\\leq16$
  • 设计状态,用f[s]表示结点子集S的色数。枚举子集进行转移。
  • $f\[S\]=min(f\[S\],1+f\[S-T\])$,T是S的子集$((T\\&S)==t)$,T中的点两两不相邻。
Last modification:March 14th, 2020 at 08:41 pm