0%

动态规划入门

发表于 更新于 分类于
动态规划入门篇~

Content

1. 从乘方和谚语说起

2. 斐波那契数列：递归受到了挑战

3. 动态规划的原理

–3.1最优子结构

–3.2重叠子问题

4.动态规划的应用

–4.1背包模型

–4.1.1 零一背包
–4.1.2 完全背包
–4.1.3 多重背包

–4.2线性动规

–4.3区间动规

5.入土

1.从乘方和谚语说起

相信你们都学习过乘方，那么我们知道:

2 X 2 X 2 X 2 X 2 X 2 X 2 X 2 X 2 X 2 =2^10=1024

那么2^11是多少呢？你会自然而然地答出2048!

好的，祝贺你已经学会了动规初步！

为什么？

我们作为人，计算2^11自然不是2X2……X2=2048这样算的

而是通过已经给出的2^10=1024计算的：2X1024=2048。

这个过程就包括了动规的核心思想之一：

记住子问题的解。

一句谚语解释：

Those who cannot remember the past, are doomed to repeat it.–George Santayana
那些忘记过去的人注定要重蹈覆辙。

2. 斐波那契数列：递归受到了挑战

对于斐波那契数列的求解，递归往往是最先考虑的解法，但是在1000ms的苛求下，递归O(2^n)的时间复杂度就比较麻烦了。

1
2
3
4
5
6
7
8
//递归解斐波那契
long long Fib(long long n)
{
    if (n==1||n==2)
        return 1;
    else
        return Fib(n - 1) + Fib(n - 2);
}

图解?

从图中可以看到，光是算fib(6)，就要重新算3遍fib(3)，时间复杂度就比较恶心了。对了，你想起什么没有？记住子问题的答案–动规登场！

1.子问题记忆法

使用一个数组来记录各个子问题的解，当再一次遇到这一问题的时候直接查找数组来获得解避免多次计算子问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//动规解决斐波那契(子问题记忆法)
int fib(int a[],int n)
{
    if (n == 0)
    {
        a[0] = 0;
        return 0;
    }
    if (n == 1)
    {
        a[1] = 1;
        return 1;
    }
    if (a[n] >= 0)
    {
        return a[n];
    }
    a[n] = fib(a, n - 1) + fib(a, n - 2);
    return fib(a, n - 1) + fib(a, n - 2);
}

2、自底向上解决方案

先求解子问题再根据子问题的解来求解父问题，斐波那契数列的子问题图如下：
1
2
3
4
5
6
7
8
9
10
11
//动规解决斐波那契(自底向上解决)
int fib(int a[],int n)
{
    a[0] = 0;
    a[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        a[i] = a[i - 1] + a[i - 2];
    }
    return a[n];
}

自底向上的计算方法实现起来非常容易，分析算法，仅从形式上面分析算法可知，算法的时间主要消耗在计算数据规模为n的数组里面的数上面了，所以时间复杂度仅为:$\color{red}\text{O(n)}$。递归在斐波那契的地位不保了！！

但是我们可以看到，在使用动规的时候，我们似乎多开了一个数组，那么空间是否会受到影响？答案是肯定的！但是在1000ms,256Mb的条件下，牺牲空间换取时间绝对是一笔很值的交♂易！

练习:LuoGu3986&钢条切割

3.动态规划的原理

最优子结构

用动态规划求解最优化问题的第一步就是刻画最优解的结构，如果一个问题的解结构包含其子问题的最优解，就称此问题具有最优子结构性质。因此，某个问题是否适合应用动态规划算法，它是否具有最优子结构性质是一个很好的线索。使用动态规划算法时，用子问题的最优解来构造原问题的最优解。因此必须考查最优解中用到的所有子问题。

重叠子问题

在斐波拉契和钢条切割中，可以看到大量的重叠子问题，比如说在求fib(6)的时候，fib(2)被调用了5次。如果使用递归算法的时候会反复求解相同的子问题，不停的调用函数，而不是生成新的子问题。如果递归算法反复求解相同的子问题，就称为具有重叠子问题性质。在动态规划算法中使用数组来保存子问题的解，问题多次求解的时候可以直接查表不用调用函数递归。

简单来说，动规就是递归再加上记录。

花小部分空间，省大部分时间。

4.动态规划的应用

4.1背包问题

1.零一背包

有N件物品和一个容量为V的背包。第i件物品的体积是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，每个物品只能选用一次,使得价值总和最大。

这是最基础的背包问题，总的来说就是：选还是不选

例题:LuoGu1048

显然，这道题并不能用贪心，因为假设你要在100时间内采药，有三个药：71时间，89价值；30时间，44价值；40时间，45价值。如果是贪心，就会果断选(71,89)，但事实上(30,44)和(40,45)更优。此时请出动规，怎么用呢？

列出状态转移方程!

对于一个物品，只有两种情况

1.第i件不放进去，这时所得价值为:dp[i-1][v]

2.第i件放进去，这时所得价值为:dp[i-1][v-c[i]]+w[i]

故状态转移方程为:

1
dp[i][v] = max(dp[i-1][v], dp[i-1][v-w[i]]+c[i])
注:零一背包可以用一维数组记录最优计划dp[v],表示不超过v体积的最大价值。

背包退火?了解一下？

2.完全背包

有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的体积是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

完全背包和01背包十分相像， 区别就是完全背包物品有无限件。总的来说就是选还是不选，选几件。

例题：LuoGu1616

列出状态转移方程

若不采这种草药，则时间花费没有增多,经过的 草药种数增加了1,采到草药价格不变,所以 dp[i][j]=dp[i-1][j];

若采这种草药,则 时间花费增加了t[i],种数增加1,采到草药价格增加了p[i],所以 dp[i][j]=dp[i-1][j-t[i]]+p[i]。

我们要使dp[i][j]$\color{red}\text{尽可能大}$,即?

1
dp[i][j]=max(dp[i-1][j],f[i-1][j-t[i]]+p[i])

这道题对于药就没有限制了，每种都无限多，所以优化出现了：

当一个药品的价值小于另一个药品的价值，并且时间高于另一个药品，我们就可以不去考虑这个药品。既然我们不是地主家的傻孩子，为什么还要花更多的时间采更少价值的药呢??

注:该问题也可以压缩到一维最优计划dp[v],我们可以将药的种类i省略 ，用后面算的值覆盖掉前面算的值.

巨佬们，背包退火?了解一下？

3.多重背包

有N种物品和一个容量为V的背包。第i种物品有n[i]个可用，每件费用是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

这里又多了一个限制条件，每个物品规定了可用的次数。

例题：LuoGu2347

我才不会告诉你我把多重背包拆成01背包来做的呢

没错，对于一般的多重背包，换成01背包水就行了，至于不一般的嘛……则可以利用倍增思想把2^i个该物品用心的一个捆绑包表示出来。

列出状态转移方程

1
f[i][v]=max(f[i-1][v-k*w[i]]+ k*c[i]|0<=k<=n[i])

4.2线性动规

其实线性动规是动规中较简单的一类题目，重点有三：

1.选对算法，正确维护

例题:LuoGu1115

2.巧妙利用前缀和

例题:LuoGu1387

3.别忘了合理递推

例题:LuoGu1052

线性递归的题个人觉得要多练，所以放了几道题，希望在刷题的过程中，你能够领悟其精髓。同时，你可以参考一个近乎万能的线性模板博客?线性动态规划

4.3区间动规

例题:LuoGu1435

典型的区间模型，回文串拥有很明显的子结构特征，即当字符串s是一个回文串时，在X两边各添加一个字符’a’后，a s a仍然是一个回文串，我们用d[i][j]来表示A[i…j]这个子串变成回文串所需要添加的最少的字符数，那么对于A[i] == A[j]的情况，很明显有

1
d[i][j] = d[i+1][j-1]

这里需要明确一点，当i+1 > j-1时也是有意义的，它代表的是空串，空串也是一个回文串，所以这种情况下d[i+1][j-1] = 0；

当A[i] != A[j]时，我们将它变成更小的子问题求解，我们有两种决策：

1.在A[j]后面添加一个字符A[i]；

2.在A[i]前面添加一个字符A[j]；

列出状态转移方程

1
2
d[i][j] = min{ d[i+1][j], d[i][j-1] } + 1; 
//每次状态转移，区间长度增加1
注：此算法空间复杂度O(n^2)，时间复杂度O(n^2)。存在优化方法，此处不与给出。