本文共 1082 字,大约阅读时间需要 3 分钟。
看见爱奇艺的一道算法题是leedcode的原题,下面是一些问题分析:
题目描述:
Given n
balloons, indexed from 0
to n-1
. Each balloon is painted with a number on it represented by array nums
. You are asked to burst all the balloons. If the you burst balloon i
you will get nums[left] * nums[i] * nums[right]
coins. Here left
and right
are adjacent indices of i
. After the burst, the left
and right
then becomes adjacent.
Find the maximum coins you can collect by bursting the balloons wisely.
问题分析:
比较好的分析:
动态规划+分治的分析策略,通过分析可以知道问题的关键时怎么切割整体,[a1,a2,a3,a4,a5,a6,......,an],将分割成两个子整体,分割点为k,则得到 N1 = [a1,a2,a3,....,a(k-1)], N2 = [a(k+1),a(k+2),.....,an]。这里分割点k的意义是踩破了第k个气球。于是把整体分成了两部分,问题在于,根据计算规则,k气球破了之后,a(k-1)和a(k+1)会变成相邻的,如果此时踩a(k-1)或者a(k+1),则都会收到另一个子整体的影响,这样的话,两个子问题就不独立,也就不能用分治了。所以关键的问题在于确定k,怎么不让子问题相互影响就是关键。扩展思维--》当只有一个元素则可以很容易求解。有两个元素也很好求解。逐次求解元素1-》2-》3.。。。-》n。dp[left][right]表示当前子问题的解:第left和第right之间位置的气球最大值。状态转换方程:
dp[left][right] = max{dp[left][right] , arr[left] * arr[i] * arr[right] + dp[left][i] + dp[i][right]};
代码:
int Solve(vector & vect){ int Len=vect.size(); Len+=2; int new_vect[Len]; for(int i=1;i
转载地址:https://blog.csdn.net/xiaochen87654321/article/details/72454513 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!