JC3 简单动态规划

horizonheart 2020-03-25

动态规划(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 型转移)
    •  小结:总结上面的内容。如果我们想用大事化小的思想解决一个问题,我们需要:
      •  设计状态。把面临的每一个问题,用状态表达出来。
      •  设计转移。写出状态转移方程,从而利用小问题的解推出大问题的解。 

相关推荐