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

这篇具有很好参考价值的文章主要介绍了算法基础复盘笔记Day11【动态规划】—— 区间DP、计数类DP、树形DP、记忆化搜索。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

第一章 区间DP

一、石子合并

1. 题目描述

设有 N 堆石子排成一排,其编号为 1 , 2 , 3 , … , N 1,2,3,…,N 123N

每堆石子有一定的质量,可以用一个整数来描述,现在要将这 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 ≤ N ≤ 300 1≤N≤300 1N300

输入样例:

4
1 3 5 2

输出样例:

22

2. 思路分析

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

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

状态转移方程: 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=n_1+n_2+…+n_k n=n1+n2++nk,其中 n 1 ≥ n 2 ≥ … ≥ n k , k ≥ n_1≥n_2≥…≥n_k,k≥ n1n2nk,k

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

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

输入格式

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

输出格式

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

由于答案可能很大,输出结果请对 1 0 9 + 7 10^9+7 109+7 取模。

数据范围

1 ≤ n ≤ 1000 1≤n≤1000 1n1000

输入样例:

5

输出样例:

7

2. 思路分析

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

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

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

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


解法二: 计数类DP

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

  • 方案中的最小值为1:则减去这个最小值1,即 f[i][j] = f[i - 1][j - 1];
  • 方案中的最小值大于1:则将每个数减去1,一共减去 j j 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 ∼ N 1∼N 1N

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

每个职员有一个快乐指数,用整数 H i H_i Hi 给出,其中 1 ≤ i ≤ N 1≤i≤N 1iN

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

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

输入格式

第一行一个整数 N。

接下来 N 行,第 i 行表示 i 号职员的快乐指数 H i H_i Hi

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

输出格式

输出最大的快乐指数。

数据范围

1 ≤ N ≤ 6000 1≤N≤6000 1N6000,
− 128 ≤ H i ≤ 127 −128≤H_i≤127 128Hi127

输入样例:

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5

输出样例:

5

2. 思路分析

算法基础复盘笔记Day11【动态规划】—— 区间DP、计数类DP、树形DP、记忆化搜索
 
考虑一颗以 u u u 为根节点的子树,这颗子树的快乐指数应该是 u u u 的函数,并且分两种情况:选 u u u 和不选 u u u

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

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

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

从根节点 u u u 开始 d f s dfs dfs 一遍即可,从根到叶深搜,从根到根返回时,做 D P DP DP,累加 f f 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 24−17−2−1 241721

在给定矩阵中,最长的滑行轨迹为 25 − 24 − 23 − … − 3 − 2 − 1 25−24−23−…−3−2−1 252423321,沿途共经过 25 个区域。

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

输入格式

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

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

输出格式

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

数据范围

1 ≤ R , C ≤ 300 1≤R,C≤300 1R,C300,
0 ≤ 矩阵中整数 ≤ 10000 0≤矩阵中整数≤10000 0矩阵中整数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

输出样例:

25

2. 思路分析

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

枚举每一个点 ( 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;
}

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


关注博主不迷路,内容持续更新中!!!文章来源地址https://www.toymoban.com/news/detail-428599.html

到了这里,关于算法基础复盘笔记Day11【动态规划】—— 区间DP、计数类DP、树形DP、记忆化搜索的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 动态规划——区间DP 学习笔记

    不含四边形不等式优化。 线性动态规划的局限性在于,它只能顺推或倒退,而不能有子区间依赖的问题。 区间动态规划是线性动态规划的扩展,它将问题划分为若干个子区间,并通过定义状态和状态转移方程来求解每个子区间的最优解,最终得到整个区间的最优解。 区间动

    2024年02月08日
    浏览(42)
  • Day36算法记录|动态规划 dp02

    步骤回顾: C语言版本写的很清楚 对应得Java版本视频解析 方法一: 动态规划 1 确定dp数组(dp table)以及下标的含义 dp[i][j] :表示从(0 ,0)出发,到(i, j) 有dp[i][j]条不同的路径。 2 . 确定递推公式 ,求dp[i][j],只能有两个方向来推导出来,即dp[i - 1][j] 和 dp[i][j - 1]。 3. dp数

    2024年02月12日
    浏览(51)
  • 区间dp(动态规划)

    动态规划(dp)是一种通过将问题分解为子问题,并利用已解决的子问题的解来求解原问题的方法。适用于具有重叠子问题和最优子结构性质的优化问题。通过定义状态和状态转移方程,动态规划可以在避免重复计算的同时找到问题的最优解,是一种高效的求解方法,常用于

    2024年02月15日
    浏览(41)
  • 动态规划——区间dp [石子合并]

    动态规划(dp)是一种通过将问题分解为子问题,并利用已解决的子问题的解来求解原问题的方法。适用于具有重叠子问题和最优子结构性质的优化问题。通过定义状态和状态转移方程,动态规划可以在避免重复计算的同时找到问题的最优解,是一种高效的求解方法,常用于

    2024年02月12日
    浏览(46)
  • 动态规划(DP)(算法笔记)

    本文内容基于《算法笔记》和官方配套练题网站“晴问算法”,是我作为小白的学习记录,如有错误还请体谅,可以留下您的宝贵意见,不胜感激。 动态规划(Dynamic Programming,DP)是一种用来解决一类最优化问题的算法思想。简单来说,动态规划将一个复杂的问题分解成若干个子

    2024年02月05日
    浏览(47)
  • 动态规划系列 | 一文搞定区间DP

    区间 DP 可以用于解决一些涉及到区间合并或分割的问题。区间 DP 通常有以下三个特点: 合并(分割) :将两个或多个部分进行整合,或者反过来将一个区间分解成多个部分。 特征 :能将问题分解为能两两合并的形式。 求解 :对整个问题设最优解,枚举合并点,将问题分

    2024年02月02日
    浏览(47)
  • 石子合并(动态规划 区间DP)+详细注释

    原题链接   活动 - AcWing 题目 设有 N 堆石子排成一排,其编号为 1,2,3,…,N。 每堆石子有一定的质量,可以用一个整数来描述,现在要将这 N 堆石子合并成为一堆。 每次只能合并相邻的两堆,合并的代价为这两堆石子的质量之和,合并后与这两堆石子相邻的石子将和新堆相

    2024年02月16日
    浏览(39)
  • 【动态规划】LeetCode 312. 戳气球 --区间DP问题

      Halo,这里是Ppeua。平时主要更新C语言,C++,数据结构算法......感兴趣就关注我吧!你定不会失望。 🌈个人主页:主页链接 🌈算法专栏:专栏链接       我会一直往里填充内容哒! 🌈LeetCode专栏:专栏链接       目前在刷初级算法的LeetBook 。若每日一题当中有力所能

    2023年04月16日
    浏览(39)
  • 动态规划算法刷题笔记【状压dp】

    a1 == 1 判断是否为奇数,如果为1,则为奇数 因为奇数二进制末位一定是1,所以 与1 得到的结果是1 这里,114——2 14 ——第15位是1,可以表示14个1 i(1j)—— 从0开始是因为,原本第1位就是1。所以j=0时,对应的就是 i 的最低位 F l o y d Floyd Fl oy d 算法: n o w ∣ f l a g = = f l

    2024年02月11日
    浏览(42)
  • 蓝桥杯备赛之动态规划篇——涂色问题(区间DP)

    2023第十四届蓝桥杯模拟赛第二期个人题解(Java实现) 2023第十四届蓝桥杯模拟赛第三期个人题解(Java实现) 蓝桥杯备赛之动态规划篇——背包问题 蓝桥杯真题——单词分析(Java实现) 😘😘 哈喽,大家好!这里是蓝桥杯系列文章的动态规划章节🔥🔥,今天要讲解的是区

    2024年01月23日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包