JC3 简单动态规划

horizonheart

2020-03-25

关注关注

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

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

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

一、基本思想

小例子：
- 上楼梯
  - 今有 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