您现在的位置是：首页 > 其他

当前栏目

算法基础复盘笔记Day11【动态规划】—— 区间DP、计数类DP、树形DP、记忆化搜索

搜索规划算法基础笔记动态 DP 区间

2023-09-11 14:20:19 时间

❤ 作者主页：欢迎来到我的技术博客😎
❀ 个人介绍：大家好，本人热衷于Java后端开发，欢迎来交流学习哦！(￣▽￣)~*
🍊 如果文章对您有帮助，记得关注、点赞、收藏、评论⭐️⭐️⭐️
📣 您的支持将是我创作的动力，让我们一起加油进步吧！！！🎉🎉

第一章区间DP

一、石子合并

1. 题目描述

设有 N 堆石子排成一排，其编号为 $1 ， 2 ， 3 ， \dots ， N$ 。

每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。

每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。

例如有 4 堆石子分别为 1 3 5 2，我们可以先合并 1、2 堆，代价为 4，得到 4 5 2，又合并 1，2堆，代价为 9，得到 9 2 ，再合并得到 11，总代价为 4+9+11=24；

如果第二步是先合并 2，3堆，则代价为 7，得到 4 7，最后一次合并代价为 11，总代价为 4+7+11=22。

问题是：找出一种合理的方法，使总的代价最小，输出最小代价。

输入格式

第一行一个数 N 表示石子的堆数 N。

第二行 N 个数，表示每堆石子的质量(均不超过 1000)。

输出格式

输出一个整数，表示最小代价。

数据范围

$1 \leq N \leq 300$

输入样例：

4
1 3 5 2

输出样例：

2. 思路分析

状态表示： f[l][r] 表示把从 $l$ 到 $r$ 合并成一堆的最小代价。

先把区间 [l, r] 切分为两部分 [l, k] 和 [k + 1, r]， $k$ 是切分点；
再把两部分 [l, k] 和 [k + 1, r] 合并在一起；
用前缀和求区间和。

状态转移方程： f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1])

初始化： f[i, i] = 0(合并每堆石子的代价为0).其余为正无穷。

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 310;

int n;
int s[N];
int f[N][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 = 2; len <= n; len ++) // 枚举区间长度
        for (int l = 1; l + len - 1 <= n; l ++) //枚举区间起点
        {
            int r = l + len - 1; //区间终点
            f[l][r] = 1e9;
            for (int k = l; k < r; 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

一、整数划分

1. 题目描述

一个正整数 n 可以表示成若干个正整数之和，形如： $n=n_1+n_2+…+n_k$ ，其中 $n_1≥n_2≥…≥n_k,k≥$ 。

我们将这样的一种表示称为正整数 n 的一种划分。

现在给定一个正整数 n，请你求出 n 共有多少种不同的划分方法。

输入格式

共一行，包含一个整数 n。

输出格式

共一行，包含一个整数，表示总划分数量。

由于答案可能很大，输出结果请对 $10^9+7$ 取模。

数据范围

$1 \leq n \leq 1000$

输入样例:

输出样例：

2. 思路分析

解法一： 完全背包解法
思路：把 $1, 2, 3, \dots n$ 分别看做 $n$ 个物体的体积，这 $n$ 个物体均无使用次数限制，问恰好能装满总体积为 $n$ 的背包的总方案数（完全背包问题变形）。

状态表示： f[i][j] 表示只从 1~i 中选，且总和等于 $j$ 的方案数。

求方案数：把集合选0个 $i$ ，1个 $i$ ，2个 $i$ ，…全部加起来。

状态转移方程: f[i][j] = f[i − 1][j] + f[i][j − i]
优化: f[j] = f[j] + f[j − i]

解法二: 计数类DP

状态表示: f[i][j] 表示总和是为 $i$ ,总个数为 $j$ 的方案数。

方案中的最小值为1：则减去这个最小值1，即 f[i][j] = f[i - 1][j - 1];
方案中的最小值大于1：则将每个数减去1，一共减去 $j$ ，方案数不变，即 f[i][j] = f[i - j][j]
状态转移方程：f[i][j] = f[i - 1][j - 1] + f[i - j][j]
方案数：res = f[n][1] + f[n][2] + .... + f[n][n]

3. 代码实现

解法一:

#include <iostream>
#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时，前 i 个物品全不选也是一种方案
    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;
}

解法二:

#include <bits/stdc++.h>

using namespace std;

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

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

int main()
{
    cin >> n;

    f[1][1] = 1; //表示总和为1，恰好是1个数的和的方案，也就是1
    for (int i = 2; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ ) //最多只有i个数，因为最小值是1，所以j最大只能取到i
            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

一、没有上司的舞会

1. 题目描述

Ural 大学有 N 名职员，编号为 $1 \sim N$ 。

他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。

每个职员有一个快乐指数，用整数 $H_i$ 给出，其中 $1 \leq i \leq N$ 。

现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。

在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。

输入格式

第一行一个整数 N。

接下来 N 行，第 i 行表示 i 号职员的快乐指数 $H_i$ 。

接下来 $N - 1$ 行，每行输入一对整数 L,K，表示 K 是 L 的直接上司。

输出格式

输出最大的快乐指数。

数据范围

$1 \leq N \leq 6000$ ,
$128≤H_i≤127$

输入样例：

输出样例：

2. 思路分析

在这里插入图片描述

考虑一颗以 $u$ 为根节点的子树，这颗子树的快乐指数应该是 $u$ 的函数，并且分两种情况：选 $u$ 和不选 $u$ 。

状态表示： f[u][1] 表示以 $u$ 为根节点的子树并且包括 $u$ 的总快乐指数，f[u][0] 表示以 $u$ 为根节点的子树并且不包括 $u$ 的总快乐指数。

状态计算：
记点 $u$ 的子节点是 $s$

选 $u$ ，f[u][1] += $\sum\limits_{}^{}$ f[s][0];
不选 $u$ ，f[u][0] += $\sum\limits_{}^{}$ max(f[s][1], f[s][0]);

从根节点 $u$ 开始 $df s$ 一遍即可，从根到叶深搜，从根到根返回时，做 $D P$ ，累加 $f$ 值。

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 6010;

int n;
int h[N], e[N], ne[N], idx;
int happy[N];
int f[N][2];
int has_fa[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]; //如果选择当前节点u，则先加上当前节点u的快乐指数
    
    for (int i = h[u]; i != -1; i = ne[i]) //遍历树
    {
        int j = e[i];
        dfs(j);
        
        f[u][1] += f[j][0];
        f[u][0] += max(f[j][0], f[j][1]);
    }
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> happy[i];
    
    memset(h, -1, sizeof h); //初始化链表
    
    for (int i = 0; i < n - 1; i ++)
    {
        int a, b;
        cin >> a >> b;
        add(b, a);
        has_fa[a] = true; //a节点有父节点
    }
    
    int root = 1; //用来找根节点 
    while (has_fa[root]) root ++; //找根节点
    
    dfs(root); //从根节点开始搜索
    
    //输出不选根节点和选根节点的最大值
    printf("%d\n", max(f[root][0], f[root][1]));
    
    return 0;
}

第四章记忆化搜索

一、滑雪

1. 题目描述

给定一个 R 行 C 列的矩阵，表示一个矩形网格滑雪场。

矩阵中第 i 行第 j 列的点表示滑雪场的第 i 行第 j 列区域的高度。

一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。

当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。

下面给出一个矩阵作为例子：

 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 - 2 - 1$ 。

在给定矩阵中，最长的滑行轨迹为 $25 - 24 - 23 - \dots - 3 - 2 - 1$ ，沿途共经过 25 个区域。

现在给定你一个二维矩阵表示滑雪场各区域的高度，请你找出在该滑雪场中能够完成的最长滑雪轨迹，并输出其长度(可经过最大区域数)。

输入格式

第一行包含两个整数 R 和 C。

接下来 R 行，每行包含 C 个整数，表示完整的二维矩阵。

输出格式

输出一个整数，表示可完成的最长滑雪长度。

数据范围

$1 \leq R, C \leq 300$ ,
$0 \leq 矩阵中整数 \leq 10000$

输入样例：

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

输出样例：

2. 思路分析

状态表示： f[i][j] 表示从点 $(i, j)$ 开始滑的路径。

枚举每一个点 $(i, j)$ ，记录从该点出发开始滑的路径：

从上面划过来： f[i][j] = f[i - 1][j]
从右边划过来：f[i][j] = f[i][j + 1]
从下面划过来：f[i][j] = f[i + 1][j]
从左边划过来：f[i][j] = f[i][j - 1]

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

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 310;

int n, m;
int g[N][N];
int f[N][N];

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

int dp(int x, int y)
{
    if (f[x][y] != -1) return f[x][y]; //如果已经计算，就可以直接返回答案了，这就是记忆化搜索，减少了重复的计算
    
    f[x][y] = 1; //v先赋值为1
    for (int i = 0; i < 4; i ++)
    {
        int a = x + dx[i], b = y + dy[i];
        if (a >= 1 && a <= n && b >= 1 && b <= m && g[x][y] > g[a][b])
            f[x][y] = max(f[x][y], dp(a, b) + 1); //更新
    }
    return f[x][y];
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            cin >> g[i][j];
    
    memset(f, -1, sizeof f); //初始化
    
    int res = 0;
    //由于可以在任意一点开始滑所以要遍历一遍滑雪场
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            res = max(res, dp(i, j));
    
    cout << res << endl;
    
    return 0;
}

创作不易，如果有收获！！！别忘记点个赞，让更多人看到！！！

关注博主不迷路，内容持续更新中！！！

猜你喜欢

剑指 Offer 24. 反转链表
linux学习参考网站
【AD小知识】QFP/TQFP/LQFP封装比较学习
工信部：推动窄带物联网、5G泛在信息基础设施
专家有奖问答|Spring Boot我该怎么学？
数据包发包工具bittwist
在windows上部署使用Redis
new FormData() 前端上传文件图片到服务器
MySQl5.6最新安装
MySQL: load data
SDRAM、DRAM及DDR FLASH ROM概念详解
关于Unity中常用的数据结构和JSON处理(专题三)

相关主题

论记忆化搜索
文本搜索
超参数搜索
仿京东搜索
数据结构-二叉搜索树
搜索的技巧
二分搜索
P17 过滤和搜索
自动搜索
记忆化搜索

zl程序教程

当前栏目

算法基础复盘笔记Day11【动态规划】—— 区间DP、计数类DP、树形DP、记忆化搜索

第一章区间DP

一、石子合并

1. 题目描述

2. 思路分析

3. 代码实现

第二章计数类DP

一、整数划分

1. 题目描述

2. 思路分析

3. 代码实现

第三章树形DP

一、没有上司的舞会

1. 题目描述

2. 思路分析

3. 代码实现

第四章记忆化搜索

一、滑雪

1. 题目描述

2. 思路分析

3. 代码实现

相关文章

当前栏目

算法基础复盘笔记Day11【动态规划】—— 区间DP、计数类DP、树形DP、记忆化搜索

第一章 区间DP

一、石子合并

1. 题目描述

2. 思路分析

3. 代码实现

第二章 计数类DP

一、整数划分

1. 题目描述

2. 思路分析

3. 代码实现

第三章 树形DP

一、没有上司的舞会

1. 题目描述

2. 思路分析

3. 代码实现

第四章 记忆化搜索

一、滑雪

1. 题目描述

2. 思路分析

3. 代码实现

相关文章

第一章区间DP

第二章计数类DP

第三章树形DP

第四章记忆化搜索