JC3 简单动态规划

动态规划（DP）不是某种具体算法，而是一种思想。

核心在于：把大问题转化为小问题，利用小问题的解推断出大问题的解。

大事化小，小事化了 的思想

一、基本思想

1.  小例子：
   • 上楼梯
     • 今有 n 级台阶。初始时站在 0 级，每次可以向上走 1 级或 2 级。问方案总数？
     •  递推关系：走到 f [ n ] ，要么是从 n-1 级走上来的，要么是从 n-2 级来的，依据加法原理
     •  f [ n ] = f [ n - 1 ] + f [ n - 2 ]

• •  硬币问题
    • 你手上有无限的面值为 1，5，11 元的硬币。给定 n，问：至少用多少枚硬币，可以恰好凑出 n 元？
    •  如果考虑贪心，先考虑11，再5，再1 ——> 但当 n = 15 时，构造方法 5+5+5 最优，显然不可行
    •  以凑 15 元为例： * 假设用了 1 元硬币，那么接下来要凑出 14 元。共 1+4=5 枚； * 假设用了 5 元硬币，那么接下来要凑出 10 元。共 1+2=3 枚； * 假设用了 11 元硬币，那么接下来要凑出  4 元。共 1+4=5 枚。
    • 这三种方案，选代价最低的，所以在这一次决策中，选择了 5 元硬币。
    • 递推关系：f [ x ] = min { 1 + f [ x-1]， 1 + f [ x-5 ]， 1 + f[ x-11 ] }

      #include <bits/stdc++.h>
      using namespace std;
      
      const int maxn=1e5+7;
      int f[maxn];  // 全局变量默认赋初值为0
      
      int main()
      {
          int n; cin>>n;
      
          for(int i=1; i<=n; i++){
              f[i]=f[i-1]+1;
              if(i-5>=0) f[i]=min(f[i], f[i-5]+1);
              if(i-11>=0) f[i]=min(f[i], f[i-11]+1);
      
              //printf("f[%d] = %d\n", i, f[i]);
          }
          
          printf("f[%d] = %d\n", i, f[i]);
      
          return 0;
      }

      Coin_1

  •  LIS问题
    •  数组的 “最长上升子序列” 是指：最长的哪一个单调上升的子序列。例如数组 a：[1，3，4，2，7，6，8，5 ] 的最长上升子序列是 1，3，4，7，8 。如何求数组的最长上升子序列？
    •  设计状态：以 f [ x ] 表示 “以 a [ x ] 结尾的上升子序列，最长有多长” ，那么，答案就是 f [ 1 ]，f [ 2 ]，…，f [ n ] 里面的最大值
    • 如何求出 f 数组？思考 f [ x ] 从哪里来。
    •  f [ x ] = max (p<x, a[p]<a[x]) { f [ p ] + 1 }；   * p<x,a[p]<a[x] 的含义是：枚举在 x 前面的，a[p] 又比 a[x] 小的那些 p。因为 a[x] 可以接到这些数的后面，形成一个更长的上升子序列

      #include <bits/stdc++.h>
      using namespace std;
      
      const int maxn=1e5+7;
      int a[maxn]={0, 1, 3, 4, 7, 2, 6, 8, 5}, n=8;
      int f[maxn];
      
      int main()
      {
          //f[1]=1;
      
          for(int x=1; x<=n; x++){
              //for(int p=1; p<x; p++)
              for(int p=0; p<x; p++)   // p要在x的前面；p从0开始，可以在max那一句把f[1]设成1
                  if(a[p]<a[x])        // a[x]可以接在a[p]的后面
                      f[x]=max(f[x], f[p]+1);
              printf("f[%d] = %d\n", x, f[x]);
          }
      
          return 0;
      }

      LIS_1

2.　总结：

• •  状态

　　　　大问题和小问题的问题形式相同，问题规模不同

　　　　如果满足这个要求，那么我们遇到的每个问题，都可以很简洁地表达。我们把可能遇到的每种 “局面” 称为状态。

　　　　想用大事化小来做关于DP的题，必须先设计状态。 如何设计状态，来完整地描述当前遇到的局面？

　　　　例如上楼梯问题中：

• • •  大问题：爬上 n 级台阶有多少种方案
    • 小问题：爬上 n - 1 级台阶有多少种方案、爬上 n - 2 级台阶有多少种方案
    • 问题形式：爬上 x x 级台阶有多少种方案
    • 设计状态：f [ x ] 表示走上 x 级的方案数

　　　　设计完状态之后，只要能利用小状态的解求出大状态的解，就可以动手把题目做出来。

• • 转移　

　　　　在前面三个例题中，我们都是先设计好状态，然后给出了一套用小状态推出大状态解的方法

　　　　从一个状态的解，得知另一个状态的解，我们称之为 “状态转移” 。这个转移式子称为 “状态转移方程”

　　　　设计转移有两种思路：

• • •  pull 型（我从哪里来）：对于一个没有求出解的状态，利用能走到它的状态，来得出它的解 code_1
    •  push 型（我到哪里去）：对于一个已经求好了解的状态，拿去更新它能走到的状态 code_2

      #include <bits/stdc++.h>
      using namespace std;
      
      const int maxn=1e5+7;
      int f[maxn];
      
      int main()
      {
          int n; cin>>n;
      
          f[0]=1;
      
          for(int i=0; i<=n; i++){
              printf("f[%d] = %d\n", i, f[i]);
      
              f[i+1]+=f[i];
              f[i+2]+=f[i];
          }
      
          return 0;
      }

      Stage_2

      #include <bits/stdc++.h>
      using namespace std;
      
      const int maxn=1e5+7;
      int f[maxn];
      
      int main()
      {
          int n; cin>>n;
      
          memset(f, 0x3f, sizeof(f));
          f[0]=0;
      
          for(int i=0; i<=n; i++){
              printf("f[%d] = %d\n", i, f[i]);
      
              f[i+1]=min(f[i+1], f[i]+1);
              f[i+5]=min(f[i+5], f[i]+1);
              f[i+11]=min(f[i+11], f[i]+1);
          }
      
          return 0;
      }

      Coin_2

      #include <bits/stdc++.h>
      using namespace std;
      
      const int maxn=1e5+7;
      int a[maxn]={0, 1, 3, 4, 7, 2, 6, 8, 5}, n=8;
      int f[maxn];
      
      int main()
      {
          for(int i=1; i<=n; i++)
              f[i]=1;
      
          for(int x=1; x<=n; x++){
              printf("f[%d] = %d\n", x, f[x]);
      
              for(int p=x+1; p<=n; p++)
                  if(a[x]<a[p])
                      f[p]=max(f[p], f[x]+1);
          }
      
          return 0;
      }

      LIS_2

• •  DP三连　　　　　

• • •  我是谁？（如何设计状态）
    •  我从哪里来？（pull 型转移）
    •  我到哪里去？（push 型转移）

• •  小结：总结上面的内容。如果我们想用大事化小的思想解决一个问题，我们需要：

• • •  设计状态。把面临的每一个问题，用状态表达出来。
    •  设计转移。写出状态转移方程，从而利用小问题的解推出大问题的解。