动态规划刷题记录(1)

这篇具有很好参考价值的文章主要介绍了动态规划刷题记录(1)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

动态规划问题在这两年蓝桥杯频繁出现,它既是一个重点,也是一个难点。

1、整数拆分

动态规划刷题记录(1)

 这道题目的思路其实很直接,基本上一眼就可以看出来这是完全背包问题的应用+一维优化。

整数N相当于是背包体积,2的幂相当于是物品体积,每种物品可以拿无数次,问你方案有多少种。数据范围已经给你了,我们可以确定最多用到2的20次方,因为2的21次方已经大于一百万了,于是我们先把2的前二十次方预处理。

接下来就是重点,我们定义集合f(i ,j)表示从前i个物品挑选使用,占用的体积为j的方案数,状态划分就是是否用了第i个物品?用了多少个?可能你没学过完全背包会看不懂我在说什么,背包问题作为动态规划的典型问题最好还是花时间学习

上代码:

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

#define N 1000100

const int mod = 1e9;

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

int main()
{
    cin >> n;

    int t = 1;
    for (int i = 0 ;i <= 21 ;i ++) p[i] = t ,t *= 2;

    f[0] = 1;
    for (int i = 0 ;i <= 21 ;i ++)
        for (int j = p[i] ;j <= n ;j ++)
            f[j] = (f[j] + f[j - p[i]]) % mod;

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

2、最大的和

动态规划刷题记录(1)

这道题目说白了就是让你在一行数中找到其中的两段,使这两段的和最大。这是一个动态规划问题,思路主要有两种:

(1)我们先来想想如果题目问你的是让你找到一个最大子段和,我们怎么解决?定义集合f(i)表示前i个数中的最大子段和,w[i]用来记录这n个数。那么以最大子段是否包含第i个数为集合划分依据:

     区间不包含w[i]: f[i] = f[i - 1];
    区间包含w[i]: f[i] = 以w[i - 1]结尾的最大连续区间和 + w[i];

那么很明显,我们缺少一个数据用来表示 以w[i - 1]结尾的最大连续区间和,所以我们再开一个区间h(i)用来记录以w[i]结尾的最大子段和。h(i)同样需要我们来递推:

        区间只包含w[i],也就是说a[i]一个数的和就大于了之前所有以w[i]结尾的子段和:h[i] = w[i];

        区间包含了w[i]: h[i] = h[i - 1] + w[i];

到这里我们就可以解决找到一个最大子段和的问题了,那么现在再想想题目的求两段最大子段和。我们完全可以正着推一遍,再反着来一遍,最后枚举中间点在哪就行了。

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

using namespace std;

#define N 1001000

int t ,f[N] ,h[N] ,g[N] ,w[N];

int main()
{
    cin >> t;
    while (t --)
    {
        int n;
        scanf("%d" ,&n);

        for (int i = 1 ;i <= n ; i ++) scanf("%d" ,&w[i]);//记录这n个数

        f[0] = g[0] = -1e9;//初始化数组,这里是个细节要注意,一般来说我们动态规划求最大值就需要初始化很小的数,求最小值就需要初始化一个很大的数。
        for (int i = 1 ;i <= n ;i ++)
        {
            h[i] = max(h[i - 1] ,0) + w[i];//其实就是h[i - 1] + w[i] 和 w[i]取最大值
            f[i] = max(f[i - 1] ,h[i]);//根据上面的递推公式
        }

        h[n + 1] = g[n + 1] = -1e9;//刚刚是1到n,现在我们n到1来一遍
        for (int i = n ;i >= 1 ;i --)
        {
            h[i] = max(h[i + 1] ,0) + w[i];
            g[i] = max(g[i + 1] ,h[i]);
        }

        int res = -1e9;
        for(int i = 1;i <= n;i ++) res = max(res, f[i] + g[i + 1]);//枚举断点,寻找最大值
        cout << res << endl;
    }

    return 0;
}

(2)第二种思路更好理解一点:f(i ,j ,0/1)表示考虑前 i个数,且已经选了 j个连续的子段,且第 i
个数是否在第 j 段中。文章来源地址https://www.toymoban.com/news/detail-492381.html

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

using namespace std;

#define N 50010

int f[N][3][2] ,a[N];

int main()
{
    int t;
    scanf("%d" ,&t);

    while (t --)
    {
        memset(f ,-0x3f ,sizeof(f));

        int n;
        scanf("%d" ,&n);

        f[0][0][0] = 0;
        for (int i = 1 ;i <= n ;i ++) scanf("%d" ,&a[i]);

        for (int i = 1 ;i <= n ; i ++)
        {
            for (int j = 0 ;j <= 2 ;j ++)
            {
                 f[i][j][1] = max(f[i - 1][j][1] + a[i] ,f[i][j][1]);//若选择第 i个数接在原先由第 i−1个数作为末尾的第 j段后面:
                 f[i][j][0] = max(max(f[i][j][1] ,f[i - 1][j][1]) ,f[i - 1][j][0]);//如果不选第i个数
                 if (j) f[i][j][1] = max(max(f[i - 1][j - 1][0] + a[i] ,f[i][j][1]) ,f[i - 1][j - 1][1] + a[i]);//如果第i个数单独开了一段
            }
        }

        cout << max(f[n][2][1] ,f[n][2][0]) << endl;
    } 
    return 0;

}

到了这里,关于动态规划刷题记录(1)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【算法日志】动态规划刷题:01背包问题,多重背包问题(day37,day38)

    目录 前言 目标和(01背包) 一和零(01背包) 零钱兑换(多重背包) 排列总和(多重背包) 这两天都是背包问题,其中的01背包的一些应用问题需要一定的数学建模能力,需要i将实际问题简化成我们熟悉的背包问题;而这两天的多重背包问题还算比较基础,但也要我明白了

    2024年02月11日
    浏览(54)
  • 【动态规划刷题 1 】 第N个泰波那契数&& 三步问题

    链接: 第N个泰波那契数 1137 . 第 N 个泰波那契数 泰波那契序列 Tn 定义如下: T0 = 0, T1 = 1, T2 = 1, 且在 n = 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2 给你整数 n,请返回第 n 个泰波那契数 Tn 的值。 示例 1: 输入:n = 4 输出:4 解释: T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4 示例 2: 输入:n = 25 输出:

    2024年02月15日
    浏览(38)
  • 力扣算法刷题Day42|动态规划:01背包问题 分割等和子集

    力扣题目:01背包问题(二维数组) 刷题时长:参考题解 解题方法:动态规划 + 二维dp数组 复杂度分析 时间 空间 问题总结 理解递推公式困难 本题收获 动规思路:两层for循环,第一层i遍历物品,第二层j枚举背包容量以内所有值 确定dp数组及下标的含义:dp[i][j] 表示从下标

    2024年02月13日
    浏览(59)
  • 力扣算法刷题Day44|动态规划:完全背包问题 零钱兑换II 组合总和Ⅳ

    力扣题目:#518.零钱兑换II(完全背包组合问题) 刷题时长:7min 解题方法:动态规划(完全背包) 复杂度分析 时间复杂度: O(mn),其中 m 是amount,n 是 coins 的长度 空间复杂度: O(m) 问题总结 对递推公式的理解 本题收获 题意转换:纯完全背包是凑成背包最大价值是多少,而本

    2024年02月13日
    浏览(39)
  • 《动态规划》刷题训练

    你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统, 如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动

    2024年01月19日
    浏览(45)
  • Leetcode 刷题 动态规划

    309. 最佳买卖股票时机含冷冻期 1. 确定dp数组以及下标的含义 具体可以区分出如下四个状态: 状态一:持有股票状态(今天买入股票,或者是之前就买入了股票然后没有操作,一直持有) 不持有股票状态,这里就有两种卖出股票状态 状态二:保持卖出股票的状态(两天前就

    2024年02月11日
    浏览(45)
  • 【C++刷题】动态规划

    这里我先声明一下dp问题的做题方法: 1.确定状态表示 2.确定状态方程 3.处理初始化问题(一般是下标的映射或者初始化保证填表正确) 4.确定填表顺序 5.根据状态表示确定返回值。 链接:点此进入 状态表示:以 i 位置为结尾的第i个斐波那契数。 状态转移方程:dp[i] = dp[i-1]

    2024年02月09日
    浏览(37)
  • 【C++刷题】【动态规划篇】(一)

    1. 题目链接:1137.第N个泰波那契数 2. 题目描述: 泰波那契序列 Tn 定义如下: T0 = 0, T1 = 1, T2 = 1, 且在 n = 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2 给你整数 n,请返回第 n 个泰波那契数 Tn 的值。 3. C++算法代码: 滚动数组优化后的C++代码: 1. 题目链接:面试题 08.01. 三步问题 2. 题目描述:

    2024年02月08日
    浏览(41)
  • 动态规划算法OJ刷题(3)

    问题描述 给出一个字符串s,分割s使得分割出的每一个子串都是回文串。计算将字符串s分割成回文串的最小切割数。例如:给定字符串s=“aab”,返回1,因为回文分割结果[“aa”,“b”]是切割一次生成的。 解题思路 方法1:用一维数组来完成,O(N^3) 注意转移方程必须是让两个

    2024年02月14日
    浏览(37)
  • 【力扣刷题】整数拆分(动态规划)

    个人简历: 全栈领域新星博主, 万粉博主、 帮助初学者入门,记录自己的学习过程 个人主页:天寒雨落的博客_CSDN博客-C,CSDN竞赛,python领域博主 热门专栏:初学者入门C语言_天寒雨落的博客-CSDN博客   目录 动态规划 整数拆分 题目 思路 代码 执行结果 其基本思想是将待求解

    2024年02月03日
    浏览(42)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包