第五章-动态规划

2025-03-16 约 2730 字预计阅读 6 分钟

https://bing.ee123.net/img/rand?artid=146302440

第五章-动态规划

写在前面：
本笔记是根据acwing网站:算法基础课进行制作的，欢迎大家支持y总，听过y总的课，你绝对会对于算法产生更深的理解和更浓厚的兴趣！
本笔记可能会有部分视频的截图，我不知道是不是会造成侵权，如果产生不好的影响，联系：2820402607@qq.com :happy:
笔者通过正儿八经跟着y总完成了18道题目，对于“动态规划”有了一定的理解，但是若要熟练掌握，还需要持之以恒地练习和努力👊
千里之行，始于足下！
ps:
y总动态规划（三）状况不是非常好，计数问题有翻车~

一、背包问题

0-1背包问题：每件物品最多只能使用一次
完全背包
多重背包及其优化
分组背包

0-1背包问题

状态表示
f ( i , j ) f(i,j)
f
(
i
,
j
)
- 集合
  - 所有选法
  - 条件：1.只从前i个物品里面选；2.总体积<=j
- 属性：如Max，Min，数量
状态计算——集合的划分
- 不重不漏
- f ( i , j )
  m a x { f ( i − 1 , j ) , f ( i − 1 , j − v i ) + w i } f(i,j) = max{f(i - 1, j),f(i - 1,j - v_i) + w_i}
  f
  (
  i
  ,
  j
  )
  =
  ma
  x
  {
  f
  (
  i
  −
  1
  ,
  j
  )
  ,
  f
  (
  i
  −
  1
  ,
  j
  −
  v
  i
  
  )

w









i




}![image-20250206163246264](https://i-blog.csdnimg.cn/img_convert/4f514e1c22ef7ce2b98943ec5212bc5c.png)

答案：

f ( N , V ) f(N,V)

(

)

DP优化

等价变换

基础做法：

//
// Created by HUAWEI on 2025/2/6.
//
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) { // 注意这个地方 i从1开始循环，否则会在下面带来数组越界！
        cin >> v[i] >> w[i];
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            f[i][j] = f[i - 1][j];
            if (j >= v[i])
                f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }
    }

    cout << f[n][m] << endl;
    return 0;
}

滚动数组：

如果在计算时只用到
f ( i ) , f ( i − 1 ) f(i),f(i - 1)
f
(
i
)
,
f
(
i
−
1
) ,那么仅仅需要声明数组
f ( 2 , N ) f(2,N)
f
(
2
,
N
) 即可！

将二维数组优化为一维数组：

//
// Created by HUAWEI on 2025/2/6.
//
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

// 基础做法
//const int N = 1010;
//
//int n, m;
//int v[N], w[N];
//int f[N][N];
//
//int main() {
//    cin >> n >> m;
//    for (int i = 1; i <= n; i++) { // 注意这个地方 i从1开始循环，否则会在下面带来数组越界！
//        cin >> v[i] >> w[i];
//    }
//
//    for (int i = 1; i <= n; i++) {
//        for (int j = 1; j <= m; j++) {
//            f[i][j] = f[i - 1][j];
//            if (j >= v[i])
//                f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
//        }
//    }
//
//    cout << f[n][m] << endl;
//    return 0;
//}

// 数组由二维变为一维
const int N = 1010;

int n, m;
int v[N], w[N];
int f[N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i];
    }

    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= v[i]; j--) {
            // 思考一下为什么这个地方要倒序？ 如果 j 正序循环的话，下面这个状态转移方程的实际含义为：
            // f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]) 显然是不对的！
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }

    cout << f[m] << endl;
    return 0;
}

完全背包问题

状态转移方程：(曲线救国~)

f ( i , j )

m a x { f ( i − 1 , j − k ⋅ v [ i ] ) + w ⋅ w [ i ] } f(i,j) = max{f(i - 1, j - k \cdot v[i]) + w \cdot w[i]}

(

)

{

(

−

⋅

[

])

⋅

[

]}

基础做法（完全类比0-1背包问题即可）能通过14/16个数据

//
// Created by HUAWEI on 2025/2/6.
// 基础做法
//
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i];
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            for (int k = 0; k * v[i] <= j; k++) {
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
            }

    cout << f[n][m] << endl;

    return 0;
}

优化基础做法：

公式推导

//
// Created by HUAWEI on 2025/2/6.
// 优化做法
//
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i];
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            f[i][j] = f[i - 1][j]; // ??? 为什么如果不这样写，而采用注释中的写法，会有一个数据点过不去？
            // 答：保证 if 语句不成立的情况下的f[i][j]的赋值
            if (j >= v[i])
                f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
//            if (j >= v[i])
//                f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]);
        }

    cout << f[n][m] << endl;

    return 0;
}

0-1背包问题和完全背包问题动态转移方程比较：

最终优化版（一维数组）

//
// Created by HUAWEI on 2025/2/6.
// 优化做法 + 1dim
//
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i];
    }
    for (int i = 1; i <= n; i++)
        for (int j = v[i]; j <= m; j++) { // 此时不需要像0-1背包问题一样从后向前遍历了
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }

    cout << f[m] << endl;

    return 0;
}

思考一下完全背包问题和多重背包问题的区别：

完全背包问题的最大值（价值）可以用一个变量来存！
多重背包问题每次求得的最大值是一个窗口内的，所以必须用单调队列来优化！

多重背包问题

暴力解法（类似于完全背包问题）：

//
// Created by HUAWEI on 2025/2/7.
//
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 110;
int n, m;
int v[N], w[N], s[N];
int f[N][N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i] >> s[i];
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            for (int k = 0; k <= s[i] and k * v[i] <= j; k++) {// 注意这里和完全背包问题的区别：多了一个约束条件
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
            }
    cout << f[n][m] << endl;


    return 0;
}

为什么不能用优化完全背包问题的做法来优化多重背包问题？

研究下面这两个公式

原因是max操作无法作减法！！！

二进制优化 + 一维数组处理：

//
// Created by HUAWEI on 2025/2/7.
//
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 11010; // new n = N * logS_max
int n, m;
int v[N], w[N];
int f[N]; // 将二维数组优化为一维数组

int main() {
    cin >> n >> m;
    int cnt = 0; // 新标号
    for (int i = 1; i <= n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        for (int k = 1; k <= c; k *= 2) {
            cnt++;
            v[cnt] = a * k;
            w[cnt] = b * k;
            c = c - k;
        }
        if (c > 0) {
            cnt++;
            v[cnt] = a * c;
            w[cnt] = b * c;
        }
    }
    n = cnt; // 更新一下 n
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= v[i]; j--) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }

    cout << f[m] << endl;

    return 0;
}

分组背包问题

在把二维数组优化为一维时，需要注意的事项：

如果在枚举时用的是上一层的数据，那么就从大到小枚举体积；如果用的是本层的数据，那就从小到大枚举体积。

//
// Created by HUAWEI on 2025/2/8.
//
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 110;
int s[N], v[N][N], w[N][N];
int f[N]; // 将二维数组优化为一维数组，降低空间复杂度！
int n, m;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        for (int j = 1; j <= s[i]; j++) {
            cin >> v[i][j] >> w[i][j];
        }
    }
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= 0; j--)
            for (int k = 0; k <= s[i]; k++) {
                // 在第i组物品中选择第几个
                if (j >= v[i][k])
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
            }

    cout << f[m] << endl;
    return 0;
}

二、线性DP

线性DP：递推方程明显的线性关系

数字三角形

如何设置DP问题中的下标？

一般是从1开始，因为运算中可能会涉及 f[i - 1]

动态规划的时间复杂度：

O ( 状态数 × 转移数 ) O(状态数 \times 转移数)
O
(
状态数
×
转移数
)

//
// Created by HUAWEI on 2025/2/8.
//
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 510, inf = 0x3f3f3f3f;
int a[N][N];
int f[N][N];
int n;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++) {
            cin >> a[i][j];
        }
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++) {
            f[i][j] = -inf;
        }
    f[1][1] = a[1][1];
    for (int i = 2; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            f[i][j] = max(f[i - 1][j], f[i - 1][j - 1]) + a[i][j];
        }
    int res = -inf;
    for (int j = 1; j <= n; j++)
        res = max(res, f[n][j]);
    cout << res << endl;
    return 0;
}

最长上升子序列

基础代码：

//
// Created by HUAWEI on 2025/2/9.
//
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 1010;

int n;
int a[N], f[N];


int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++) {
        f[i] = 1;
        for (int j = 1; j <= i - 1; j++) {
            if (a[j] < a[i])
                f[i] = max(f[i], f[j] + 1);
        }
    }

    int res = -1e9;
    for (int i = 1; i <= n; i++) {
        res = max(res, f[i]);
    }

    cout << res << endl;
    return 0;
}

上述代码时间复杂度：

O ( n 2 ) O(n^2)

(

)

记录最长上升子序列的方案代码：使用一个数组记录一下转移过程中上个子序列的最后数字的序号即可，略

优化方法：

横坐标表示以x长度的最长上升子序列，纵坐标表示该序列结尾的值。

目录

第五章-动态规划

第五章-动态规划