【C语言】Leetcode-312 戳气球

文章目录


题目

链接: Leetcode-312 戳气球

在这里插入图片描述


思路

我们观察戳气球的操作,发现这会导致两个气球从不相邻变成相邻,使得后续操作难以处理。于是我们倒过来看这些操作,将全过程看作是每次添加一个气球。

首先
我们需要创建一个 v a l val val 数组,用来存储所有的元素,其中 v a l [ 0 ] val[0] val[0] v a l [ n u m s S i z e + 1 ] val[numsSize+1] val[numsSize+1] 的位置用来存放两头的超出数组边界的1,剩下的从1开始就是 n u m s nums nums 数组里的元素

然后
我们定义 s o l v e solve solve 方法,令 s l o v e ( i , j ) slove(i,j) slove(i,j) 表示开区间 ( i , j ) (i,j) (i,j) 内的位置全部填满气球能够得到的最多硬币数。由于时开区间,因此区间两端的气球编号就是 v a l [ i [ val[i[ val[i[ v a l [ j ] val[j] val[j]

接着
我们要对这个 s l o v e slove slove 方法进行分类讨论

i > = j − 1 i >= j-1 i>=j1 时,开区间中没有气球, s l o v e ( i , j ) slove(i,j) slove(i,j) 的值为0

i < j − 1 i < j-1 i<j1 时,我们美剧开区间 ( i , j ) (i,j) (i,j) 内的全部位置 m i d mid mid ,令 m i d mid mid 为当前区间第一个添加的气球,该操作能得到的硬币数为 v a l [ i ] ∗ v a l [ m i d ] ∗ v a l [ j ] val[i] * val[mid] * val[j] val[i]val[mid]val[j]

同时我们利用递归,去计算分割出的两区间对 s o l v e ( i , j ) solve(i,j) solve(i,j) 的贡献,这三项之和的最大值,即为 s o l v e ( i , j ) solve(i,j) solve(i,j) 的值

还有
因为我们是利用递归将每种结果都计算出来,所以他的工程量是很大的,为了降低时间复杂度,我们可以建立一个二维数组,来根据 l e f t left left r i g h t right right 的值存放这个开区间内的最大贡献量

代码如下

int rec[302][302];
int val[302];

int solve(int left, int right) {
    if (left >= right - 1)
        return 0;
    if (rec[left][right] != -1)
        return rec[left][right];
    for (int i = left + 1; i < right; i++) {
        int sum = val[left] * val[i] * val[right];
        sum += solve(left, i) + solve(i, right);
        rec[left][right] = fmax(rec[left][right], sum);
    }
    return rec[left][right];
}

int maxCoins(int* nums, int numsSize) {
    memset(rec, -1, sizeof(rec));
    val[0] = val[numsSize + 1] = 1;
    for (int i = 1; i <= numsSize; i++) {
        val[i] = nums[i - 1];
    }
    return solve(0, numsSize + 1);
}

相关推荐

  1. LeetCode-day07-312. 气球

    2024-06-10 09:52:05       32 阅读
  2. 困难 Leetcode 312. 气球 区间dp/记忆化搜索

    2024-06-10 09:52:05       40 阅读
  3. [C语言]时间

    2024-06-10 09:52:05       70 阅读
  4. 13 递归求解气球

    2024-06-10 09:52:05       64 阅读
  5. c#,获取时间

    2024-06-10 09:52:05       67 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-06-10 09:52:05       172 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-06-10 09:52:05       190 阅读
  3. 在Django里面运行非项目文件

    2024-06-10 09:52:05       158 阅读
  4. Python语言-面向对象

    2024-06-10 09:52:05       171 阅读

热门阅读

  1. 1341. 电影评分

    2024-06-10 09:52:05       48 阅读
  2. 如何学好量子计算机技术的两种思路

    2024-06-10 09:52:05       38 阅读
  3. 爬山算法详细介绍

    2024-06-10 09:52:05       54 阅读
  4. 4. 流程控制语句

    2024-06-10 09:52:05       42 阅读
  5. vscode 好用的插件

    2024-06-10 09:52:05       42 阅读
  6. 23种设计模式——创建型模式

    2024-06-10 09:52:05       45 阅读
  7. 2024年6月10日--6月16日(渲染+ue独立游戏)

    2024-06-10 09:52:05       44 阅读
  8. Terminal Multiplexer的使用

    2024-06-10 09:52:05       46 阅读
  9. 什么情况下需要用到动态IP

    2024-06-10 09:52:05       45 阅读