循环的遍历

  • 注意一下最内层的循环是什么，他决定了这一步的决策是什么。

例题

纸币问题 2

  • 这一题要我们求完全背包的方案数（考虑顺序）
  • 那么内层循环应该放的是面额的遍历，因为最后一步的面额是不一定的。

  • 正确写法✔：

    1
    2
    3
    4
    for(int i=1;i<=w;i++)
       for(int j=1;j<=n;j++)
          if(i>=a[j])
            dp[i]=(dp[i-a[j]]+dp[i])%mod;

  • 错误写法❌：

    1
    2
    3
    4
    5
    6
    for(int i=1;i<=n;i++){
        ll x; cin>>x;
        for(int j=x;j<=w;j++){
            dp[j]=(dp[j-x]+dp[j])%mod;
        }
    }
  • 为什么下面那个是错误的？
  • 因为把当前面额作为内层循环，相当于固定了最后一步只能是这个面额，没法考虑到顺序问题。这样的话第二次只能在第一次的基础上增加。实际上，第一次的面额也可以在第二次的基础上增加。因此这个做法是不正确的。
    注意：下面那个方法因为只考虑了最开始的顺序(即输入顺序)，所以只有一种顺序，那么就可以拿来统计组合数

在解决这类问题时，关键要问自己：

  • 题目要求的是组合数还是排列数？
  • 我的循环顺序是否允许不同的支付顺序？
  • 我是否在无意中强加了某种顺序限制？(关键点)
    对于这道题，既然要求考虑支付顺序，就必须使用金额在外层的循环方式。

特殊例题

计算容积不超过n得到的最大的占有体积

  • 思路：设$dp[i]$表示不超过i获得的最大值，那么每一个物品的体积是x，价值也是x。
  • 状态转移方程：

    例题

考前临时抱佛脚 - 洛谷

  • 题目说可以双核，那么只要一边最接近sum/2就彳亍了，所以可以用上面那个模型

    01背包0也有值的问题

  • 在正常的01背包中，如果遍历不到就不管了，但是现在要求不能放入时也有一定的值，那么这时就要管了，在体积不够时，每一个都只有一种选法，那就是不选。所以每一个都要加上不选所对应的值。

    例题：

5 倍经验日 - 洛谷

  • 题目说了在打不过时也能得到经验，你要是不给玩家经验，当然是不对的啦

DP的一般思路

  • 首先看看是否是背包或者背包的变形，要是是的话就简单了
  • 看一下每一次有几种转移方式，把可能的变化列一下，看看是否有规律
  • 在这一讲还是不用区分特殊类型的DP的