第五章-动态规划

发布于：2025-03-17 ⋅ 阅读:(20) ⋅ 点赞:(0)

第五章-动态规划

写在前面：

本笔记是根据acwing网站:算法基础课进行制作的，欢迎大家支持y总，听过y总的课，你绝对会对于算法产生更深的理解和更浓厚的兴趣！

本笔记可能会有部分视频的截图，我不知道是不是会造成侵权，如果产生不好的影响，联系：2820402607@qq.com :happy:

笔者通过正儿八经跟着y总完成了18道题目，对于“动态规划”有了一定的理解，但是若要熟练掌握，还需要持之以恒地练习和努力👊

千里之行，始于足下！

ps:

y总动态规划（三）状况不是非常好，计数问题有翻车~

文章目录

一、背包问题

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

0-1背包问题

DP

  • 状态表示 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)=max{f(i−1,j),f(i−1,j−vi​)+wi​}
    image-20250206163246264

答案： f ( N , V ) 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]\} f(i,j)=max{f(i−1,j−k⋅v[i])+w⋅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;
}

优化基础做法：

公式推导

image-20250206214837291

//
// 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背包问题和完全背包问题动态转移方程比较：

image-20250206222933250

最终优化版（一维数组）

//
// 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;
}

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

  • 研究下面这两个公式

image-20250207205013284

  • 原因是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;
}

分组背包问题

image-20250208004303999

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

  • 如果在枚举时用的是上一层的数据，那么就从大到小枚举体积；如果用的是本层的数据，那就从小到大枚举体积。
//
// 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：递推方程明显的线性关系

数字三角形

image-20250208142010850

如何设置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;
}

最长上升子序列

image-20250209200532135

基础代码：

//
// 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) O(n2)

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

优化方法：

image-20250218170548998

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

补充：整数二分
image-20250218175226928

如何理解：

image-20250218175502038

这里我尝试不用y总的方法，而是用程序设计助教的方法去做~

//
// Created by HUAWEI on 2025/2/18.
// 注意这个题目中整数二分法的使用
//
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1e5 + 10;
int a[N];
int q[N]; // 动态更新不同长度最长上升子序列的末值
int n;


int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    int len = 0; // 最大长度
    for (int i = 1; i <= n; i++) {
        int l = 0, r = len + 1;
        while (r - l > 1) {
            // 整数二分
            int mid = (r + l) >> 1;
            if (q[mid] >= a[i])
                r = mid;
            else
                l = mid;
        }
        len = max(len, l + 1);
        q[l + 1] = a[i];
    }
    cout << len << endl;
    return 0;
}

最长公共子序列

image-20250209232439725

如何理解00，01，10，11？

  • 不选a[i] 不选b[j]
  • 不选a[i] 选b[j]
  • …

代码如下：

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

using namespace std;

const int N = 1010;
char a[N], b[N];
int f[N][N];
int n, m;

int main() {
    scanf("%d%d", &n, &m);
    scanf("%s%s", a + 1, b + 1); // 注意细节，从第一个字符的位置读入

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

    printf("%d\n", f[n][m]);

    return 0;
}

最短编辑距离

补充：

如何理解DP？

  • DP是对于暴搜的一种优化，每个状态表示很多个情况！而暴搜是对于每种情况进行简单地枚举。
  • 以空间换时间！

分析：
image-20250218204130069

代码：

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

using namespace std;

const int N = 1010;

int n, m;
char a[N], b[N];
int f[N][N];

int main() {
    scanf("%d%s", &n, a + 1);
    scanf("%d%s", &m, b + 1);

    // 初始化f数组
    for (int i = 1; i <= n; i++) {
        f[i][0] = i;
    }
    for (int j = 1; j <= m; j++) {
        f[0][j] = j;
    }

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            if (a[i] == b[j])
                f[i][j] = min(f[i][j], f[i - 1][j - 1]);
            else
                f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
        }

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


    return 0;
}

编辑距离

代码：

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

using namespace std;


const int N = 1010, M = 20;

char str[N][M];
int f[M][M];
int n, m;

int edit_len(char a[], char b[]) {
    // int f[M][M];
    int la = strlen(a + 1), lb = strlen(b + 1);
    // 初始化
    for (int i = 1; i <= la; i++)
        f[i][0] = i;
    for (int j = 1; j <= lb; j++)
        f[0][j] = j;

    for (int i = 1; i <= la; i++)
        for (int j = 1; j <= lb; j++) {
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] != b[j]));
        }
    return f[la][lb];
}


int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%s", str[i] + 1);

    for (int i = 1; i <= m; i++) {
        char s[M];
        int len;
        scanf("%s%d", s + 1, &len);

        int res = 0;
        for (int j = 1; j <= n; j++) {
            if (edit_len(str[j], s) <= len) {
                res++;
            }
        }
        printf("%d\n", res);
    }

    return 0;
}

注：

  • 我遇到了一个很抽象的问题，如果将f构建在edit_len函数里面，就不能通过；如果构建在全局，就可以通过；
  • 怀疑是acwing OJ自身的问题！

三、区间DP

石子合并

状态转移方程：

image-20250215162437092

注：

  • s[N]:前缀数组

需要想一下如何循环~

动态规划的递归写法——记忆化搜索

区间DP的一般模式：

  1. 先循环区间长度从小到大
  2. 在循环区间的左端点
//
// Created by HUAWEI on 2025/2/15.
//
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 310;

int s[N];
int f[N][N];
int n;


int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> s[i];
    for (int i = 1; i <= n; i++)
        s[i] += s[i - 1]; // 前缀数组

    for (int len = 1; len <= n - 1; len++)
        for (int i = 1; i <= n - len; i++) {
            int l = i;
            int r = i + len;
            f[l][r] = 1e9;
            for (int k = l; k <= r - 1; k++) {
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
            }
        }

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

四、计数类DP

整数划分

法一：

完全背包问题的思想

image-20250220162121699

如何理解 f [ i ] [ j ] f[i][j] f[i][j] ?

  • 前 i i i个数，加和的值为 j j j
  • 状态转移方程： f ( i , j ) = f ( i − 1 , j ) + f ( i − 1 , j − i ) + . . . + f ( i − 1 , j − s i ) f(i,j) = f(i - 1, j) + f(i - 1, j - i) + ... + f(i - 1, j - s i) f(i,j)=f(i−1,j)+f(i−1,j−i)+...+f(i−1,j−si) (其实隐含的就是第 i i i 个数选几个)

如何进行优化？
f ( i , j ) = f ( i − 1 , j ) + f ( i − 1 , j − i ) + f ( i − 1 , j − 2 i ) . . . + f ( i − 1 , j − s i ) f ( i , j − i ) = f ( i − 1 , j − i ) + f ( i − 1 , j − 2 i ) + . . . + f ( j − s i ) f(i,j) = f(i - 1, j) + f(i - 1, j - i) + f(i - 1, j - 2i) ... + f(i - 1, j - s i) \\ f(i, j - i) = f(i - 1, j - i) + f(i - 1, j - 2i) + ... + f(j - si) f(i,j)=f(i−1,j)+f(i−1,j−i)+f(i−1,j−2i)...+f(i−1,j−si)f(i,j−i)=f(i−1,j−i)+f(i−1,j−2i)+...+f(j−si)
所以我们可以得到：
f ( i , j ) = f ( i − 1 , j ) + f ( i , j − i ) f(i, j) = f(i - 1, j) + f(i, j - i) f(i,j)=f(i−1,j)+f(i,j−i)
注意可以将高维数组优化为一维数组，注意第二层循环是从前向后遍历！

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

using namespace std;

const int N = 1010, mod = 1e9 + 7;

int n;
int f[N];


int main() {
    cin >> n;

    f[0] = 1; // 无论是多少个数相加，最终加和为0，方案只有一种

    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++) {
            f[j] = (f[j] + f[j - i]) % mod;
        }

    cout << f[n] << endl;


    return 0;
}

法二：

另辟蹊径~

image-20250220175454097

这个方法太抽象了，很难自己想到

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

using namespace std;

const int N = 1010, mod = 1e9 + 7;

int n;
int f[N][N];

int main() {
    cin >> n;

    // 初始化
    f[1][1] = 1;

    for (int i = 2; i <= n; i++)
        for (int j = 1; j <= i; j++) {
            f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod;
        }

    int res = 0;
    for (int i = 1; i <= n; i++)
        res = (res + f[n][i]) % mod;

    cout << res << endl;

    return 0;
}

五、数位统计DP

计数问题

分类讨论

举例说明：

image-20250225153359238
image-20250316115627138

上图是针对于 x > 0 x > 0 x>0 的情况，如果 x = 0 x = 0 x=0 ,需要注意前导零的处理，在情况一这里：

image-20250316115835444

需要将 000 改为 001

代码如下：

//
// Created by HUAWEI on 2025/3/16.
//
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

int power10(int x) {
    int res = 1;
    while (x--) {
        res *= 10;
    }
    return res;
}

int get_(vector<int> num, int h, int l) {
    int res = 0;
    for (int i = h; i >= l; i--) {
        res = 10 * res + num[i];
    }
    return res;
}

int count_num(int x, int s) { // s 代表需要计数的数字
    if (!x)
        return 0; // count_num 计算的是 1 ~ x 之间每个数字出现的次数，需要对于 x == 0 进行特判
    vector<int> num;

    while (x) {
        // num 中高位在后，低位在前
        num.push_back(x % 10);
        x = x / 10;
    }

    int n = num.size(), res = 0;
    for (int i = n - 1 - !s; i >= 0; i--) {
        // 计算 d 位 0 的个数时， 如果 d 位是最高位，则不需要计算，因为不可能存在这种情况
        if (i < (n - 1)) // 如果 d 是最高位，分类中的第一种情况直接不讨论
            res += (get_(num, n - 1, i + 1) - !s) * power10(i);

        if (num[i] == s) {
            res += get_(num, i - 1, 0) + 1;
        } else if (num[i] > s) {
            res += power10(i);
        }

    }
    return res;
}

int main() {
    int a, b;
    while (cin >> a >> b, a) {
        if (a > b)
            swap(a, b);
        for (int i = 0; i < 10; i++) {
            cout << count_num(b, i) - count_num(a - 1, i) << " ";
        }
        cout << endl;
    }

    return 0;
}

注意：

  • 采用前缀和类似的思想，计算出 count_num(b, i) 和 count_num(a - 1, i) 作差即可
  • 对于每一位（d）出现的数字进行枚举，可以考虑d一般的位置，随后在针对d位于首位进行特判分析
  • 先在纸上分析明白再去编写代码
  • 一定要考虑清楚先导零的情况！

六、状态压缩DP

有明显的特点：

n 必须满足 n < 20 n < 20 n<20

蒙德里安的梦想

状态实际是一个整数，但是要把它看作二进制数

以下理解给后来可能有疑惑的同学：
1、题目等价于按照列来横着放置小方块。（其他人写的行放置小方块）
2、f(i,j):摆放第i列，i-1列伸出来横着的方格状态为j的方案数，j为一个二进制数，范围是0～行数位数的二进制范围；
3、i-1列转移到i列满足：(j & k) == 0,其中k是i-1列的状态；
4、同时每个有效的状态满足：j | k 不存在连续奇数个零，即每个格子只能用纵向的格子来填；

又及

f[i, j]的i是从0开始的，0是第一列，m - 1是最后一列，所以f[m, 0]是指第m - 1列摆满的方案数。同理f[i, j]表示第i - 1列伸出的状态是j的方案数。

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

#define int long long

using namespace std;

const int N = 13, M = 1 << 13;
bool st[M];
int f[N][M];

signed main() {
    int n, m;
    while (cin >> n >> m, n | m) {
        int sol_num = 1 << n;

        // 处理st, 方便判断是否存在连续奇数个0
        for (int i = 0; i < sol_num; i++) {
            st[i] = true;
            int cnt = 0; // 连续 0 的个数
            for (int j = 0; j < n; j++) {
                if (i >> j & 1) {
                    if (cnt & 1)
                        st[i] = false;
                    cnt = 0;
                } else {
                    cnt++;
                }
            }
            if (cnt & 1)
                st[i] = false;
        }

        memset(f, 0, sizeof f); // 处理每组数据时记得都要初始化f
        // 初始化f数组
        f[0][0] = 1;
        for (int i = 1; i <= m; i++)
            for (int j = 0; j < sol_num; j++)
                for (int k = 0; k < sol_num; k++) {
                    if (st[k | j] and !(k & j))
                        f[i][j] += f[i - 1][k];
                }
        cout << f[m][0] << endl;
    }


    return 0;
}

有几个易错点记一下：

  • 动态规划最外层的枚举范围
  • 处理多组数据时记得每次都要初始化
  • 位运算的优先级

最短Hamilton路径

image-20250310195510590 
//
// Created by HUAWEI on 2025/3/10.
//

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 22, M = 1 << N;
int w[N][N];
int f[M][N];


int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> w[i][j];

    memset(f, 0x3f, sizeof f);
    f[1][0] = 0; // 注意如何初始化的

    for (int i = 0; i < (1 << n); i++)
        for (int j = 0; j < n; j++) {
            if (i >> j & 1) {
                for (int k = 0; k < n; k++) {
                    if (i >> k & 1) {
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
                    }
                }
            }
        }

    cout << f[(1 << n) - 1][n - 1] << endl;
    return 0;
}

需要注意的地方：

  • 代码中 i，j, k 的表示和讲解视频中的一样， i 表示的是经过路径的状态压缩表示， j 表示的是走到的目标点， k 表示的是倒数第二个结点，如下公式所示：

i ⇝ k → j i \leadsto k \rightarrow j i⇝k→j

七、树形DP

没有上司的舞会(树形DP最为经典的一个问题)

image-20250313145910731

状态转移方程如下：

f ( u , 0 ) = Σ    m a x ( f ( s i , 0 ) , f ( s i , 1 ) ) f ( u , 1 ) = Σ    f ( s i , 0 ) + h ( u ) f(u, 0) = \Sigma \; max (f(s_i, 0), f(s_i, 1)) \\ f(u, 1) = \Sigma \; f(s_i, 0) + h(u) f(u,0)=Σmax(f(si​,0),f(si​,1))f(u,1)=Σf(si​,0)+h(u)
时间复杂度分析：

  • 每个结点计算 f ( u , 0 ) , f ( u , 1 ) f(u, 0), f(u, 1) f(u,0),f(u,1) 时间复杂度： 2 n 2n 2n
  • 在计算 f ( u , 0 ) , f ( u , 1 ) f(u, 0), f(u, 1) f(u,0),f(u,1) 时需要考虑到 u u u 的所有孩子，而这棵树总的孩子数量应该是边数 m = n − 1 m = n - 1 m=n−1
  • 所以时间复杂度： O ( n ) O(n) O(n)
//
// Created by HUAWEI on 2025/3/13.
//
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 6010;
int happy[N];
int h[N], e[N], ne[N], idx; // 把链式前向星的板子倍数
int f[N][2];
bool root_if[N]; // 找到根节点

void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

void dfs(int u) {
    f[u][1] += happy[u];
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        dfs(j);

        f[u][0] += max(f[j][0], f[j][1]);
        f[u][1] += f[j][0];
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> happy[i];

    memset(h, -1, sizeof(h)); // 使用链式前向星一定记得初始化 h 数组

    for (int i = 0; i < n - 1; i++) {
        int l, k;
        cin >> l >> k;
        add(k, l);
        root_if[l] = true;
    }

    int root = 1;
    while (root_if[root]) {
        root++; //找到根节点
    }

    dfs(root);

    cout << max(f[root][0], f[root][1]) << endl;


    return 0;
}

需要注意的点：

  • 链式前向星如何使用！把板子背下来
    • for (int i = h[u]; ~i; i = ne[i]) 中 ~i的使用
    • memset(h, -1, sizeof(h)); // 使用链式前向星一定记得初始化 h 数组

八、记忆化搜索

前面所用的都是循环的写法来写，本部分研究递归的写法。

记忆化搜索的优点：

  • 代码复杂度很小，但是时间会稍微长一点，而且递归的层数如果很多的话可能会爆栈

滑雪

搜索过程不能存在环（环形依赖）！

  • 这一点是显然成立的！可以想一想为什么！
image-20250313174933374

基础版代码：

//
// Created by HUAWEI on 2025/3/13.
//
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 310;
int g[N][N], f[N][N];
int r, c;

int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};

int dp(int x, int y) {
    int &v = f[x][y]; // 坐标原点定为矩阵的左上角
    if (v != -1)
        return v;
    v = 1;
    for (int i = 0; i <= 3; i++) {
        if (x + dx[i] <= r and x + dx[i] >= 1 and y + dy[i] <= c and y + dy[i] >= 1 and
            g[x + dx[i]][y + dy[i]] < g[x][y]) {
            v = max(v, 1 + dp(x + dx[i], y + dy[i]));
        }
    }
    return v;
}

int main() {
    scanf("%d%d", &r, &c);
    for (int i = 1; i <= r; i++)
        for (int j = 1; j <= c; j++) {
            scanf("%d", &g[i][j]);
        }

    memset(f, -1, sizeof f);

    int res = 0;
    for (int i = 1; i <= r; i++)
        for (int j = 1; j <= c; j++) {
            res = max(res, dp(i, j));
        }

    printf("%d\n", res);
    return 0;
}

提示：

  • 把矩阵边缘设置为inf 可以减少递归时的判断条件

注意：

  • 初始化 memset(f, -1, sizeof f) !

优化版代码：

//
// Created by HUAWEI on 2025/3/13.
//
#include<iostream>
#include<cstring>
#include<algorithm>

#define inf 0x3f3f3f3f
using namespace std;

const int N = 310;
int g[N][N], f[N][N];
int r, c;

int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};

int dp(int x, int y) {
    int &v = f[x][y]; // 坐标原点定为矩阵的左上角
    if (v != -1)
        return v;
    v = 1;
    for (int i = 0; i <= 3; i++) {
        int a = x + dx[i], b = y + dy[i];
        if (g[a][b] < g[x][y])
            v = max(v, 1 + dp(a, b));
    }
    return v;
}

int main() {
    scanf("%d%d", &r, &c);
    for (int i = 1; i <= r; i++)
        for (int j = 1; j <= c; j++) {
            scanf("%d", &g[i][j]);
        }
    for (int i = 0; i <= r + 1; i++)
        for (int j = 0; j <= c + 1; j++) {
            if (i == 0 or i == r + 1 or j == 0 or j == c + 1)
                g[i][j] = inf;
        }
    memset(f, -1, sizeof f);

    int res = 0;
    for (int i = 1; i <= r; i++)
        for (int j = 1; j <= c; j++) {
            res = max(res, dp(i, j));
        }

    printf("%d\n", res);
    return 0;
}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布