动态规划经典入门

动态规划入门到熟悉，看不懂来打我啊

如果你是我的读者，你更希望整本书的风格是：
1、上文（尽量解释详细，小白能看懂）
2、本文（解释比较偏学术/概念/标准化/简单，但是看起来可能比较费劲）
非常希望你在本文末尾投票，你的决定会影响本书风格。

动态规划专题

一. 线性DP

**1. 数字三角形 **

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5
1
2
3
4
5

转换思路，从下向上求出答案

状态转移方程式：a[ i ] [ j ] = max(a[i + 1] [j], a[i + 1] [j + 1])

**2. 最长递增子序列 **

给定一个长度为N的数列，求数值严格单调递增的子序列的长度最长是多少。

# d[i] 表示前i个数中最大单调递增的子序列的长度
# 对于当前的数ai, 遍历1~ i-1 中的数，如果ai > aj, 则d[i] = d[j] + 1
for(int i = 0; i < n; i++){
        d[i] = 1;
        for(int j = 0; j < i; j++){
            if(a[i] > a[j])
                d[i] = max(d[i], d[j] + 1);
        }
        ans = max(ans, d[i]);
    }
cout << ans << endl;
1
2
3
4
5
6
7
8
9
10
11

3.数字和最大的递增子序列

给定你一个数字序列，找出数字和最大的递增子序列

思路：跟前一个思路一样采用dp的思想，现在dp[ i ]的含义表示为序列中第i个元素结尾的数字和的最大值

for(int i=0;i<n;i++){
    	dp[i] = a[i];
        for(int j=0;j<i;j++){
            if(a[i]>a[j])dp[i] = max(dp[j]+a[i], dp[i]);//dp【i】表示以第i个元素结尾的数字和的最大值
        }
        Max=max(Max,dp[i]);  //记录最大的数字和
    }
1
2
3
4
5
6
7

4.最长公共子序列

给定两个长度分别为N和M的字符串A和B，求既是A的子序列又是B的子序列的字符串长度最长是多少。

# d[i][j] 表示字符串A的前i个字符与字符串B的前j个字符含有的最大公共子序列的长度
for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++){
        if(s1[i - 1] == s2[j - 1])d[i][j] = d[i - 1][j - 1] + 1;
        else d[i][j] = max(d[i - 1][j], d[i][j - 1]);
 
}
1
2
3
4
5
6
7

5.acwing902.最短编辑距离

给定两个字符串A和B，现在要将A经过若干操作变为B，可进行的操作有：

1. 删除–将字符串A中的某个字符删除。
2. 插入–在字符串A的某个位置插入某个字符。
3. 替换–将字符串A中的某个字符替换为另一个字符。

现在请你求出，将A变为B至少需要进行多少次操作。

将一个字符串通过删除、插入、替换变为另一个字符串的最短距离,可以用动态规划来做，用f(i, j)来表示长度为i的字符串变为长度为j的字符串最小的操作次数，那么如何来求f(i, j)呢？对每个字符我们有3种操作:

1.删除：假设删除a[i]后，a[1 ~ i] 与 b[1 ~ j] 匹配，那么说明a[1 ~ i - 1]已经与b[1 ~ j]相等了，那么多出来的a[i]直接删掉即可，状态转移方程为：f(i, j) = f(i - 1, j) + 1

2.插入： 假设插入一个a[i],使a[i] == b[j]后，a[1 ~ i] 与 b[1 ~ j] 匹配,那么说明a[1 ~ i]已经与b[i ~ j - 1]相等了，要使a[1 ~ i]与b[i ~ j]相等,只需再a[1 ~ i]的后面添加一个b[j]即可

状态转移方程为：f(i, j) = f(i, j - 1) + 1

3.替换：假设将a[i]替换成b[j],使得a[1 ~ i] 与 b[1 ~ j] 匹配,那么说明a[1 ~ i - 1]已经与b[i ~ j - 1]相等了，要使a[1 ~ i]与b[i ~ j]相等,只需将a[i]替换为b[j]即可。

如果a[i] = b[j]，则无需替换，状态转移方程为：f(i, j) = f(i - 1, j - 1)

如果a[i] != b[j]，则需要替换，状态转移方程为：f(i, j) = f(i - 1, j - 1) + 1
1
2
3
4
5
6
7
8
9
10
11
12
13

二.背包问题

01背包问题

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

基本思路
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。

用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。

这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f [i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。

注意f[i][v]有意义当且仅当存在一个前i件物品的子集，其费用总和为v。所以按照这个方程递推完毕后，最终的答案并不一定是f[N] [V]，而是f[N][0…V]的最大值。如果将状态的定义中的“恰”字去掉，在转移方程中就要再加入一项f[i][v-1]，这样就可以保证f[N] [V]就是最后的答案。至于为什么这样就可以，由你自己来体会了。

优化空间复杂度
以上方法的时间和空间复杂度均为O(N*V)，其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(V)。

先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1…N，每次算出来二维数组f[i][0…V]的所有值。那么，如果只用一个数组f [0…V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1] [v-c[i]]两个子问题递推而来，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1][v -c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V…0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i -1][v-c[i]]的值。伪代码如下：

for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
1
2
3

其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程f[i][v]=max{f[i-1][v],f[i- 1][v-c[i]]}，因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了f[i][v]由f[i][v-c[i]]推知，与本题意不符，但它却是另一个重要的背包问题P02最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的。

总结
01背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法，状态转移方程的意义，以及最后怎样优化的空间复杂度。

搜索

• 通过不停的试探去寻找解的一种算法
• 与其说是一种算法，不如说是一种方法（递归的思想）
• 基础的方法有暴力的搜索法，深搜，广搜

引入 （图的遍历）

从图的任意指定顶点出发，依照某种规则去访问图中所有顶点，且每个顶点仅被访问一次，这一过程叫做图的遍历。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mD9vUWQ4-1663291975443)(C:\Users\ADMINI~1\AppData\Local\Temp\1612006121967.png)]

图的遍历按照深度优先和广度优先规则去实施，通常有深度优先遍历法（Depth_First Search——DFS ）和 广度优先遍历法（ Breadth_Frist Search——BFS）两种。

---

深度优先遍历

方法：1、访问指定的起始顶点；
2、若当前访问的顶点的邻接顶点有未被访问的（通过标记数组实现），则任选一个访问；反之，退回到 最近访问过的顶点；直到与起始顶点相通的全部顶点都访问完毕；
3、若此时图中尚有顶点未被访问，则再选其中一个顶点作为起始顶点并访问之，转 2； 反之，遍历结束。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vWGq6aAg-1663291975444)(C:\Users\Administrator\AppData\Roaming\Typora\typora-user-images\image-20210131084211317.png)]
一条道走到黑，走不完再倒回去

---

广度优先遍历

方法：从图的某一结点出发，首先依次访问该结点的所有邻 接顶点 V1, V2, …, Vn 再按这些顶点被访问的先后次序依次访问 与它们相邻接的所有未被访问的顶点，重复此过程，直至所有顶点均被访问为止。

一层一层的走

---

深度搜索 （DFS）

算法过程

状态A（我是谁，我在哪）

• 判断当前状态是否满足题目需要，满足则进行保存，比较，输出等操作
• 判断当前状态是否合法（当前状态是否满足题目要求，或者数组是否越界），满足继续执行否则回到上次调用
• 往下走一层，递归调用dfs()

例题一：

求出n的全排列

1：全排列函数

//全排列的函数：next_permutation（start,end），和prev_permutation（start,end）。这两个函数作用是一样的，区别就在于前者求的是当前排列的下一个排列，后一个求的是当前排列的上一个排列。
//当前序列不存在下一个排列时，函数返回false，否则返回true
#include 
#include //用此头文件
using namespace std;
int arr[1000];
int main(void)
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)arr[i] = i + 1;
    do{//采用do-while循环，用来输出初始的序列
        for (int i = 0; i < n; i++) cout << arr[i] << ' ';
        cout << endl;
    }while (next_permutation(arr, arr + n));
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2：深搜

#include 
#include 

using namespace std;
int arr[1000];
int book[1000];
int n;
void dfs(int step)//step表示当前处于第step个盒子
{
    if (step == n + 1)//如果当前处于第n+1个盒子，说明n个盒子已经处理完成，输出序列
    {
        for (int i = 1; i <= n; i++)cout << arr[i] << ' ';
        cout << endl;
        return;//返回到第n个盒子继续处理,特别注意，否则卡死
    }
    for (int i = 1; i <= n; i++)
    {//每次遍历1-n的数字，如果此数字之前没有被用过(book[i]=0)，则可以填到盒子里面
        if (!book[i])
        {//核心操作（其中1,2,4需要根据实际情况变化）
         //   1：首先将遍历过的进行标记
         //   2：将当前状态赋值
         //   3：递归搜索
         //   4：回到当前状态以后，之前的标记要消除
            book[i] = 1;
            arr[step] = i;
            dfs(step + 1);
            book[i] = 0;
        }
    }
}
int main(void)
{
    cin >> n;
    dfs(1);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

例题二

整数划分（搜索剪枝：去除一些显然不可能的情况，减少搜索次数）

一个正整数可以划分为多个正整数的和，比如n=6时： 6；1＋5；2＋4；3+3；2+2+2；1+1+4；1+2+3；1+1+1+3；1+1+2+2；1+1+1+1+2；1+1+1+1+1+1 共有十一种划分方法。 　　给出一个正整数，问有多少种划分方法。

基本思路：正整数n可以看成n个小球，每一个小球代表数字一，观察可知划分即为将这n个小球放入k的盒子里面，且每一个盒子不能为空，则k依次为从1到n，k=n时即为n个1相加。每次搜索k个盒子

//最基本的朴素搜索（必不能AC）
#include 
#include 
using namespace std;
int arr[1000];
int n;
int sum;
void dfs(int step,int k)//step表示当前处于第step个盒子
{
    if (step == k + 1)
    {
        int num = 0;
        for (int i = 1; i <= n; i++)
            num += arr[i];
        if (num == n)
        {  
            printf("%d=%d",n,arr[1]);
            for (int i = 2; i <= k; i++)
                printf("+%d", arr[i]);
            cout << endl; 
            sum++;
        }
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        arr[step] = i;//数字可以重复使用无需标记
        if (arr[step] >= arr[step - 1])
        {//因为1 2 3和3 2 1是同一种情况，所以让后一个数小于等于前一个数防止重复
            dfs(step + 1, k);
        }
    }
}
int main(void)
{
    cin >> n;
    for(int i=1;i<=n;i++)
        dfs(1,i);
    cout << sum;
    return 0;
}



//剪枝算法
#include 
#include 
using namespace std;
int arr[1000];
int n;
int sum;
void dfs(int step, int k, int m)//m表示剩余数字的和，即还没有填的数的和
{

    if (step == k+1)
    {   //如果step==k+1,并且sum=0,表明全部盒子填完且符合情况，输出
        if (m == 0)
        {
            printf("%d=%d", n, arr[1]);
            for (int i = 2; i <= k; i++)
                printf("+%d", arr[i]);
            cout << endl;
            sum++;
        }
        return;
    }
    for (int i = arr[step - 1]; i <= m / (k - step + 1); i++)//上下界剪枝
    {
        arr[step] = i;
        //保证前面的数字小于后面的数字，每次从step-1开始枚举，且保证枚举的数字不能超过后面总和的平均数
        //例如1 2 3 4,为一组解，那么在枚举arr[3]的时候，此时sum = 7,sum/(k-step+1)=3.5，则arr[3]不能超过3，否则arr[4]必定比arr[3]要小
        //不满足前面的数字比后面的数字大，造成重复计算
        dfs(step + 1, k, m-i);//尝试arr[step]=i后，sum-i;
    }
}
int main(void)
{
    cin >> n;
    arr[0] = 1;//因为有step-1的情况，就把arr[0]设为1
    for (int i = 1; i <= n; i++)
    {
        dfs(1, i, n);
    }
    cout << sum;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

例题三

迷宫问题

定义一个n行n列的二维数组

例如当n等于5时有
0  1  0  0  0
0  1  0  1  0
0  0  0  0  0
0  1  1  1  0
0  0  0  1  0
1
2
3
4
5
6

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

基本思路：从起点出发，每次按照顺序遍历四个方向尝试所有情况，如果合法就进入下一层

#include 
#include 
using namespace std;
typedef long long ll;
ll n, m, min = 0x3fffffff;
ll arr[501][501], book[501][501];//book为标记数组
ll dx[] = {0,1,0,-1};//x方向上的
ll dy[] = {1,0,-1,0};//y方向上的
void dfs(int x, int y, ll step)//x,y表示当前所在的点的横纵坐标,step表示当前的步数
{
    ll tx, ty, k;
    if (x == n - 1 && y == n - 1)//如果当前所在位置是终点，说明已经走完
    {
        if (step < min)//如果比最短路径还要小，更新min
            min = step;
        return;//一定要return 
    }
    for (k = 0; k < 4; k++)
    {
        tx = x + dx[k];//利用此方法，算出下一个需要走的点的坐标
        ty = y + dy[k];
        if (tx<0 || tx>n-1 || ty<0 || ty>n-1)//判断边界，如果越界就不执行
            continue;
        if (book[tx][ty] == 0 && arr[tx][ty] == 0)
        {
            book[tx][ty] = 1;
            dfs(tx, ty, step + 1);//搜素下个点
            book[tx][ty] = 0;
        }
    }
}

int main(void)
{
    ll i, j;
    scanf("%lld", &n);
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
            scanf("%lld", &arr[i][j]);
    }
    book[0][0] = 1;//起点首先标记
    dfs(0, 0, 0);//从起点开始搜索
    printf("%lld\n", min);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

广度搜索

解决迷宫问题，一层一层的解决，依次找出一步可以到达的点，两步，三步，…可以到达的点。将每次走过的点加入队列来进行扩展。

数组形态

#include 
#include 

using namespace std;
int arr[501][501];
int book[501][501];
int dx[] ={ 0,1,0,-1 };//规定四个方向
int dy[]= { 1,0,-1,0 };
struct f {
    int x;
    int y;
    int s;
}map[2500];
int n;
void bfs()
{
    int tail = 1, head = 1;//将起点入队
    map[tail].x = 0, map[tail].y = 0;
    map[tail].s = 0;
    book[0][0] = 1;//标记起点
    tail++;
    while (head < tail)
    {
        int k = 0;
        for (int i = 0; i < 4; i++)//遍历四个方向
        {
            int nx = map[head].x + dx[i];//计算下一个方向
            int ny = map[head].y + dy[i];
            if (nx<0 || nx>n - 1 || ny<0 || ny>n - 1)
                continue;
            if (book[nx][ny] == 0 && arr[nx][ny] == 0)
            {
                book[nx][ny] = 1;
                map[tail].x = nx;//更新队列
                map[tail].y = ny;
                map[tail].s = map[head].s + 1;//等于父亲步数加一
                tail++;
            }
            if (nx == n-1 && ny == n-1)//如果等于终点
            {
                k = 1;
                cout << map[tail - 1].s;//注意要减一
                break;
            }
        }   if (k == 1)
            break;
        head++;//四个方向探索完毕后，head++模拟出队效果

    }
}
int main(void)
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            scanf("%d", &arr[i][j]);
    }
    bfs();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

stl形态

#include 
#include 
#include 
using namespace std;
typedef long long ll;
ll arr[501][501];
ll book[501][501];
ll dx[] = {0,1,0,-1};//x方向上的
ll dy[] = {1,0,-1,0};//y方向上的
struct f {//定义结构体
    int x;//表示横坐标
    int y;//纵坐标
    int s;//走过的步数
};
queuequ;//定义维护的队列
ll n;
void bfs()
{
    struct  f a;
    a.x = 0;//设置起点位置并加入队列
    a.y = 0;
    a.s = 0;
    qu.push(a);
    book[0][0] = 1;//首先将起点标记
    while (!qu.empty())//如果队列不为空
    {
        int k = 0;
        struct f b = qu.front();//每次取队首元素
        qu.pop();//取出之后就弹出
        for (int i = 0; i < 4; i++)
        {
            struct f c;
            c.x = b.x + dx[i];
            c.y = b.y + dy[i];
            c.s = b.s + 1;
            if (c.x<0 || c.x>n - 1 || c.y<0 || c.y>n - 1)
                continue;
            if (book[c.x][c.y] == 0 && arr[c.x][c.y] == 0)//如果这个点可以走且没有标记过，就加入队列
            {
                book[c.x][c.y] = 1;
                qu.push(c);
                if (c.x == n - 1 && c.y == n - 1)//如果是终点就输出
                {
                    k = 1;
                    cout << c.s;
                    break;
                }
            }
        }
        if (k)break;
    }
}
int main(void)
{
    ll i, j;
    scanf("%lld", &n);
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
            scanf("%lld", &arr[i][j]);
    }
    bfs();
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

迷宫问题输出路径

基本思路：结构体增加一个变量记录当前点的父亲点的坐标，从终点开始，递归找到最短路径上的每一个点的坐标并打印

#include 
#include 

using namespace std;
int arr[501][501];
int book[501][501];
int dx[] = { 0,1,0,-1 };//规定四个方向
int dy[] = { 1,0,-1,0 };
struct f {
    int x;
    int y;
    int s;
    int f;//记录其父亲的标号
}map[2500];
int n;
void print(int x)//函数功能：打印下标为x的点的坐标
{
    if (map[x].f != -1)//如果其父亲不是起点，就执行递归
    {
        print(map[x].f);
        printf("( %d , %d )\n", map[x].x, map[x].y);//打印的坐标
    }
}
void bfs()
{
    int tail = 1, head = 1;//将起点入队
    map[tail].x = 0, map[tail].y = 0;
    map[tail].s = 0, map[tail].f = -1;
    book[0][0] = 1;//标记起点
    tail++;
    while (head < tail)
    {
        int k = 0;
        for (int i = 0; i < 4; i++)//遍历四个方向
        {
            int nx = map[head].x + dx[i];//计算下一个方向
            int ny = map[head].y + dy[i];
            if (nx<0 || nx>n - 1 || ny<0 || ny>n - 1)
                continue;
            if (book[nx][ny] == 0 && arr[nx][ny] == 0)
            {
                book[nx][ny] = 1;
                map[tail].x = nx;//更新队列
                map[tail].y = ny;
                map[tail].s = map[head].s + 1;//等于父亲步数加一
                map[tail].f = head;//记录其父亲
                tail++;
            }
            if (nx == n - 1 && ny == n - 1)//如果等于终点
            {
                k = 1;
                cout << map[tail - 1].s<> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            scanf("%d", &arr[i][j]);
    }
    bfs();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74