首页 > 其他分享 >戳气球 动态规划

戳气球 动态规划

时间:2024-11-05 13:20:07浏览次数:1  
标签:nums int -- 开区间 动态 规划 气球 dp

n 个气球,编号为0n - 1,每个气球上都标有一个数字,这些数字存在数组 nums 中。现在要求戳破所有的气球。戳破第 i 个气球,可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1i + 1 超出了数组的边界,那么就当它是一个数字为 1 的气球。

求所能获得硬币的最大数量。

  • n == nums.length
  • 1 <= n <= 300
  • 0 <= nums[i] <= 100

示例 1:

输入:nums = [3,1,5,8]
输出:167
解释:
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167

一道区间DP,在做的时候先考虑了闭区间,也就是 \(dp[i][j]\) 表示 戳掉了 \([i,j]\) 这个闭区间中所有气球得到的最大收益,递推公式如下:

\[dp[i][j]=dp[i][k-1]+dp[k+1][j]+a[k]*a[i-1]*a[j+1] \]

这样做如果直接三层循环,在 \(i=j\) 以及 \(i=j-1\) 时,数组是不更新的,需要提前初始化;并且 \(k\) 选点的时候只会选取 \([i+1,j-1]\) 这个区间中的值,不会选到 \(i\) 或者 \(j\) ,但实际情况对于闭区间 \([i,j]\) 最后戳破的气球可能是这个闭区间上的任意一点。在此基础上继续修改会使代码变得更加复杂,于是改为下面开区间的做法:

\(dp[i][j]\) 表示戳掉开区间 \((i,j)\) 中所有气球得到的最大收益,最终结果为 \(dp[0][n+1]\)。递推公式为:

\[dp[i][j]=dp[i][k]+dp[k][j]+a[i]*a[k]*a[j] \]

由于是开区间,\(i,j,k\) 都是之前未取到的,所以 \(dp[i][k]\) 和 \(dp[k][j]\) 可以无缝衔接,取 \(k\) 点的收益为 \(a[i]*a[k]*a[j]\) 。

其次在具体实现中,为不添加多余的边界特判,可以将 \(nums[0] \sim nums[n-1]\) 变到 \(a[1]\sim a[n]\) ,之后初始化 \(a[0]=a[n+1]=1\)。

具体代码如下:

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n=nums.size();
        vector<int>a(n+2);
        for(int i=0;i<n;i++)a[i+1]=nums[i];
        vector<vector<int>>dp(n+2,vector<int>(n+2));
        a[0]=a[n+1]=1;
        for(int len=2;len<=n+1;len++){
            for(int i=0;i<=n;i++){
                int j=i+len;
                if(j>n+1)break;
                for(int k=i+1;k<j;k++)
                    dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[k]*a[j]);
            }
        }
        return dp[0][n+1];
    }
};

标签:nums,int,--,开区间,动态,规划,气球,dp
From: https://www.cnblogs.com/sunmk/p/18527632

相关文章

  • 如何解决传统能源企业后备人才不足、人才规划缺失问题
    如何解决传统能源企业后备人才不足、人才规划缺失问题很多传统能源企业都面临着老员工逐渐退休,新员工还没有培养起来的问题,缺乏提前对人力资源规划的意识,导致当企业要开展新业务时或者老员工离职的时候,缺乏合适的人选。特别是对于国有企业来说,人才全流程管理体系化不足,导致员......
  • 动态生成表-判断表是否存在性能对比
    SHOWTABLESLIKE查询直接使用SHOWTABLESLIKE'table_name'来判断表是否存在。结果为空表示表不存在。$tableName='your_table_name';$res=Db::query("SHOWTABLESLIKE'{$tableName}'");if(empty($res)){echo"表不存在";}else{......
  • 73页满分PPT | 智能制造-供应链管理战略项目规划方案书
    这份PPT是一份全面的智能制造与供应链管理战略项目规划方案书,涵盖了企业C2M策略、供应链战略及现状认识、项目总体思路与需求理解、项目实施方案与交付成果,以及综合项目实施计划等多个方面,旨在通过智能化和信息化手段,实现供应链的优化和管理效率的提升,以支持企业的服务导向和多......
  • 算法笔记:Day-09(初始动态规划)
    509.斐波那契数斐波那契数(通常用F(n)表示)形成的序列称为斐波那契数列。该数列由0和1开始,后面的每一项数字都是前面两项数字的和。也就是:F(0)=0,F(1)=1F(n)=F(n-1)+F(n-2),其中n>1给定n,请计算F(n)。示例1:输入:n=2输出:1解释:F(2)=F(1)......
  • 动态内存分配
    一、为什么要有动态内存分配二、malloc和free栈区中的数据出了作用域就会销毁;而静态区中数据的生命周期与全局变量一致,出了作用域也不会被销毁,直至程序结束后才会销毁。malloc函数与free函数需要包含的头文件是<stdlib.h>①malloc②free#include<stdio.h>#includ......
  • 【c++篇】:深入剖析vector--模拟实现属于自己的c++动态数组
    ✨感谢您阅读本篇文章,文章内容是个人学习笔记的整理,如果哪里有误的话还请您指正噢✨✨个人主页:余辉zmh–CSDN博客✨文章所属专栏:c++篇–CSDN博客文章目录前言一.`vector`类的默认成员函数整体框架构造函数析构函数拷贝构造函数赋值运算符重载函数测试二.`vector`......
  • ArkUI常用数据处理:掌握Map操作与动态数据管理
    在HarmonyOS应用开发中,ArkUI框架提供了丰富的数据处理能力,尤其是对于Map这类非线性容器的操作。本文将详细介绍ArkUI中Map的基本概念、操作方法,以及如何在实际开发中应用Map进行数据处理和动态数据管理。Map的重要性Map是非线性容器的一种,它提供了快速查找、插入和删除键值......
  • (算法)分割等和⼦集————<动态规划>
    1.题⽬链接:416.分割等和⼦集2.题⽬描述:3.解法(动态规划):算法思路:先将问题转化成我们「熟悉」的题型。如果数组能够被分成两个相同元素之和相同的⼦集,那么原数组必须有下⾯⼏个性质:        i.所有元素之和应该是⼀个偶数;        ii.数组中最⼤的......
  • (算法) ⽬标和————<动态规划>
    1.题⽬链接:494.⽬标和2.题⽬描述: 3.解法(动态规划):算法思路:本题可以直接⽤「暴搜」的⽅法解决。但是稍微⽤数学知识分析⼀下,就能转化成我们常⻅的「背包模型」的问题。设我们最终选取的结果中,前⾯加+号的数字之和为a,前⾯加-号的数字之和为b,整个数组的总和......
  • 智慧园区算法视频分析服务器烟雾识别智慧园区安防视频监控及动态布控预警方案
    智慧园区安防视频监控及动态布控预警方案是一种综合性的安全管理解决方案,智慧园区算法视频分析服务器通过结合视频监控技术、人工智能算法、大数据分析等技术,实现对工厂区域内人、车、物的全面监控和管理。一、需求和目标1、系统建设目标:目标是构建一个重点区域的动态人脸识别......