首页 > 代码库 > DP基础

DP基础

 

DP基础

  • 简单dp
  • 背包问题
  • 记忆化搜索

简单dp

数字三角形

给一个数字构成的三角形,求从顶端走到底部的一条路径,使得路径上的和最大(或者最小)。

        1
2 3
6 5 4
Example_1
7
3 8
8 1 0
5 2 6 100000
Example_2

根据Example_2可以知道贪心显然是不正确的。
可以看出,除了两边的点以外,每个点可以上一层的两个位置之一到达当前点。
如果我们知道上一层的从顶端到达两个位置的最大路径值,那么对于当前点来说,必然选择较大的那个位置转移过来,也就得到了顶端到达当前位置的最大值。
以Example_1为例,

    dp[1] = 1;
dp[2] = dp[1] + 2 = 3;
dp[3] = dp[1] + 3 = 4;
dp[6] = dp[2] + 6 = 11;
dp[5] = max(dp[2], dp[3]) + 5 = 9;
dp[4] = dp[3] + 4 = 8;

最长上升子序列

技术分享 个数,求上升子序列的最长长度。

上升子序列,即找到 技术分享,满足 技术分享

7
1 7 3 5 9 4 8

最长上升子序列长度为4,其中一种可行的方案为1,3,5,9。

做法

  1. 技术分享
    技术分享表示以第技术分享个数结尾的上升子序列的最长长度。
for (int i = 1; i <= n; ++i) {    f[i] = 1;    for (int j = 1; j < i; ++j)        if (a[j] < a[i])            f[i] = max(f[i], f[j] + 1);}
  1. 技术分享
    对于当前位置的数 技术分享 来说,就是要找到比它小的数结尾的上升子序列的最长长度,用 技术分享 表示以数值 技术分享 结尾的上子序列的最长长度,结合树状数组或者线段树维护区间 技术分享 的最大长度值即可。
    技术分享 比较大(比如技术分享)时,需要对数值先进行离散化

离散化,可以简单地理解为将非常大、不连续的值映射成较小的、连续的值,一一对应。

/*** 离散化*/vector<int> V;for (int i = 1; i <= n; ++i)    V.push_back(a[i]);// 排序sort(V.begin(), V.end());// 去重V.erase(unique(V.begin(), V.end()), V.end());// 二分映射位置(0 ~ n - 1)for (int i = 1; i <= n; ++i)    a[i] = lower_bound(V.begin(), V.end(), a[i]) - V.begin();

背包问题

  • 01背包
  • 完全背包
  • 多重背包

01背包

有一个空间为技术分享的背包,有技术分享件物品可以选择装入背包,每个物品有价值技术分享和体积技术分享,求在空间允许的情况下装入的物品价值和最大

简要分析:空间固定的情况下,价值肯定越大越好。或者反过来想,在价值固定的情况下,空间越小越好。

// f[i]表示空间为i时的最大价值。for (int i = 1; i <= n; ++i) // 枚举物品    for (int j = W; j >= w[i]; --j) // 倒着做,避免同一物品装入多次        f[j] = max(f[j], f[j - w[i]] + v[i]);

完全背包

背包空间为技术分享,有技术分享物品,每种物品有价值技术分享和体积技术分享,每种物品有无数件,求背包能装入的最大价值。

简要分析:与01背包的区别在于,一种物品是只有一件还是无数件,01背包是倒着做来避免同一物品装入多次,那么完全背包反过来就可以了。

// f[i]表示空间为i时的最大价值。for (int i = 1; i <= n; ++i) // 枚举物品    for (int j = w[i]; j <= W; ++j) // 正着做,同一物品可以装入多次        f[j] = max(f[j], f[j - w[i]] + v[i]);

多重背包

多重背包介于01背包和完全背包之间,每种物品的数量限制为技术分享个。

分析:对于每种物品,如果把它视为技术分享种物品,每种物品只能取一件,就转化成了01背包问题。但是技术分享可能非常大,导致复杂度(技术分享)过高。这时候需要做一些优化工作。已知用1、2、4、8可以组合0~15的任意一个数值。
二进制下,0~15的数值最多有4位,0000~1111。
技术分享,所以对于0~15的数值化为二进制后根据相应位是否为1就可以知道由1、2、4、8哪些数构成。例如,技术分享
回到背包问题上,我们可以将技术分享分成技术分享种物品(最多技术分享种),每种物品的数量为1,这样理论上可以组合出技术分享中的任意数量。时间复杂度降为技术分享

记忆化搜索

本质上还是DP,但是状态之间的转移写成了dfs的形式,所以计算过程中可以减少一些不必要的状态,以及方便边界处理。

POJ 1088 滑雪

Description
Michael喜欢滑雪百这并不奇怪, 因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12/ 11 10 9
一个人可以从某个点滑向上下左右相邻四个点之一,当且仅当高度减小。在上面的例子中,一条可滑行的滑坡为24-17-16-1。当然25-24-23-…-3-2-1更长。事实上,这是最长的一条。
Input
输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行,每行有C个整数,代表高度h,0<=h<=10000。
Output
输出最长区域的长度。
Sample Input
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
Sample Output
25

分析:对当前位置(x, y)来说,当满足高度大小关系的时候,可以连接到(x - 1, y)、(x, y + 1)、(x + 1, y)和(x, y - 1)。
当然可以将所有位置按高度排序,然后按顺序去DP,时间复杂度为技术分享
用记忆化搜索的方法做的话,dfs(x, y)表示从(x, y)出发的最长长度,技术分享, 当技术分享
因为从(x, y)出发的最长长度是固定的,不存在什么限制条件,所以可以用技术分享表示dfs(x, y),令技术分享初值为-1,当访问dfs(x, y)时若技术分享不为-1,说明技术分享计算过了,直接返回技术分享即可,这样就避免了重复计算。
当(x, y)超出边界时,直接返回0即可。

 
<style></style>

DP基础