赞
踩
312. 戳气球
有 n 个气球,编号为0 到 n-1,每个气球上都标有一个数字,这些数字存在数组 nums 中。
现在要求你戳破所有的气球。如果你戳破气球 i ,就可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后,气球 left 和气球 right 就变成了相邻的气球。
求所能获得硬币的最大数量。
说明:
你可以假设 nums[-1] = nums[n] = 1,但注意它们不是真实存在的所以并不能被戳破。
0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100
这一题的主要难点在于动态规划的状态转移方程,如果用暴力算法,时间复杂度为O(n!),当n=500时,可想而知肯定超时,随后我就想到了dp,但是我不知道怎么状态转移,因为每戳破一个气球,原气球的排列顺序就会改变,因此需要换一个思路,在膜拜完题解大佬的思路后,我尝试着用大佬的思路解题,思路:
解决了状态转移方程,问题就解决了一大半,我们只需要考虑边界问题
k的取值范围很好解决,应该在 i+1 ~ j-1 这个范围
那么怎么循环i和j呢?
由状态转移方程可知,如果想知道 F [ i ] [ j ] ,那么从矩阵的 i行 j列 往下往左都应该是已知的,你可以斜着循环也可以从最后一行往第一行循环,最后只要返回F [ 0 ] [ -1 ] 即可
class
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。