【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>=j−1 时，开区间中没有气球， s l o v e ( i , j ) slove(i,j) slove(i,j) 的值为0

  当 i