[已解决]Python：每日一题 271

zltzlt

今天的题目：

有 n 个气球，编号为 0 到 n-1，每个气球都有一个分数，存在 nums 数组中。每次吹 j 号气球可以得到的分数为 nums[left] * nums[j] * nums[right]，left 和 right 分别表示 j 号气球相邻的两个气球。当 j 号气球被吹爆后，其左右两气球即为相邻。要求返回吹爆所有气球得到最多的分数。

注意：nums 不为空。

样例 1：

输入：[4, 1, 5, 10]
输出：270
解释：
nums = [4, 1, 5, 10] 吹爆 1，得分 4 * 1 * 5 = 20
nums = [4, 5, 10]   吹爆 5, 得分 4 * 5 * 10 = 200
nums = [4, 10]   吹爆 4，得分 1 * 4 * 10 = 40
nums = [10]   吹爆 10，得分 1 * 10 * 1 = 10
总得分为 20 + 200 + 40 + 10 = 270。

样例 2：

输入：[3,1,5]
输出：35
解释：
nums = [3, 1, 5] 吹爆 1，得分 3 * 1 * 5 = 15
nums = [3, 5] 吹爆 3，得分 1 * 3 * 5 = 15
nums = [5] 吹爆 5，得分 1 * 5 * 1 = 5
总得分为 15 + 15 + 5  = 35。

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

华一仙

2019-11-9 13:19:15

1. """
   
2. 我的理解：
   
3.                                  l-----m-----r
   
4.                                  |     |     |
   
5. nums: [3, 1, 5, 8] -> new_nums: [1, 3, 1, 5, 8, 1]
   
6. 
   
7. 对于上方 new_nums 这种情况
   
8. => dp[l][r] = dp[l][m] + dp[m][r] + new_nums[l] * new_nums[m] * new_nums[r]
   
9.    dp[l][r]: 吹爆 l 与 r 之间的气球，但不包括 l 和 r；不同的 m 可能有不同的 dp[l][r]
   
10. """
    
11. def f271(nums):
    
12.     new = [1] + [i for i in nums if i] + [1]    # 删去对结果没有影响的 0，并补齐两侧默认的 1
    
13.     n = len(new)
    
14.     dp = [[0]*n for _ in range(n)]
    
15.     for gap in range(2, n):                     # 从 3 个一组，到 n 个一组
    
16.         for l in range(n - gap):
    
17.             r = l + gap
    
18.             tmp = new[l] * new[r]               # 避免重复计算
    
19.             for m in range(l + 1, r):
    
20.                 dp[l][r] = max(dp[l][r], dp[l][m] + dp[m][r] + tmp * new[m])
    
21.     return dp[0][-1]

复制代码

跳转到最佳答案楼层

华一仙

1. """
   
2. 我的理解：
   
3.                                  l-----m-----r
   
4.                                  |     |     |
   
5. nums: [3, 1, 5, 8] -> new_nums: [1, 3, 1, 5, 8, 1]
   
6. 
   
7. 对于上方 new_nums 这种情况
   
8. => dp[l][r] = dp[l][m] + dp[m][r] + new_nums[l] * new_nums[m] * new_nums[r]
   
9.    dp[l][r]: 吹爆 l 与 r 之间的气球，但不包括 l 和 r；不同的 m 可能有不同的 dp[l][r]
   
10. """
    
11. def f271(nums):
    
12.     new = [1] + [i for i in nums if i] + [1]    # 删去对结果没有影响的 0，并补齐两侧默认的 1
    
13.     n = len(new)
    
14.     dp = [[0]*n for _ in range(n)]
    
15.     for gap in range(2, n):                     # 从 3 个一组，到 n 个一组
    
16.         for l in range(n - gap):
    
17.             r = l + gap
    
18.             tmp = new[l] * new[r]               # 避免重复计算
    
19.             for m in range(l + 1, r):
    
20.                 dp[l][r] = max(dp[l][r], dp[l][m] + dp[m][r] + tmp * new[m])
    
21.     return dp[0][-1]

复制代码

阴阳神万物主

这种帖子，允许抢沙发吗？允许的话，我就抢一回。

zltzlt

阴阳神万物主 发表于 2019-11-9 13:22
这种帖子，允许抢沙发吗？允许的话，我就抢一回。

阴阳神万物主

提问：当一开始就没有提供气球怎么算？没提供气球给吹的话……是默认给一分吗？

塔利班

还有0分负分这种坑么

zltzlt

塔利班 发表于 2019-11-9 13:35
还有0分负分这种坑么

没有负分 ，但是有 0 分

WXF666

捏爆哪个才能最大呢。。

塔利班

1. def ball(X):
   
2.     results=[]
   
3.     def f(X,lastsum):
   
4.         if len(X)==1:
   
5.             return X[0]
   
6.         elif len(X)==2:
   
7.             return lastsum+X[0]*X[1]+max(X)
   
8.         else:
   
9.             for i in range(1,len(X)-1):
   
10.                 temp=X[:]
    
11.                 # print(i,len(X))
    
12.                 mul=X[i]*X[i-1]*X[i+1]
    
13.                 temp.pop(i)
    
14.                 results.append(f(temp,mul+lastsum))
    
15.     f(X,0)
    
16.     return max([e for e in results if e])
    
17. 
    
18. print(ball([3,1,5]))
    
19. print(ball([4, 1, 5, 10]))

复制代码

zltzlt

塔利班 发表于 2019-11-9 16:20

输入 [10] 报错：ValueError: max() arg is an empty sequence

塔利班

zltzlt 发表于 2019-11-9 16:23
输入 [10] 报错：ValueError: max() arg is an empty sequence

都加上到列表里就好了

1. def ball(X):
   
2.     results=[]
   
3.     def f(X,lastsum):
   
4.         if len(X)==1:
   
5.             results.append(X[0])
   
6.         elif len(X)==2:
   
7.             results.append(lastsum+X[0]*X[1]+max(X))
   
8.         else:
   
9.             for i in range(1,len(X)-1):
   
10.                 temp=X[:]
    
11.                 mul=X[i]*X[i-1]*X[i+1]
    
12.                 temp.pop(i)
    
13.                 f(temp,mul+lastsum)
    
14.     f(X,0)
    
15.     return max(results)
    
16. 
    
17. print(ball([3,1,5]))
    
18. print(ball([4, 1, 5, 10]))
    
19. print(ball([10]))

复制代码

阴阳神万物主

但愿不要超过最大递归深度

1. def solve(nums:'至少有一个元素的整数数组',tot:'int 基础分数'=0)->'int 最多分数':
   
2.     le = len(nums)
   
3.     res = tot
   
4.     #print('调试',nums,tot)
   
5.     for j in range(le):
   
6.         mul = nums[j]
   
7.         if j > 0:
   
8.             mul *= nums[j-1]
   
9.         if j < le-1:
   
10.             mul *= nums[j+1]
    
11.         tot += mul
    
12.         #print('调试 吹爆',nums[j])
    
13.         get = solve(nums[:j]+nums[j+1:],tot)
    
14.         if get > res:
    
15.             res = get
    
16.         tot -= mul
    
17.         #print('调试 恢复',nums[j])
    
18.     return res
    
19. 
    
20. if __name__ == '__main__':
    
21.     print('示例1 270 输出：',solve([4,1,5,10]))
    
22.     print('示例2 35 输出：',solve([3,1,5]))
    

复制代码

zltzlt

塔利班 发表于 2019-11-9 16:25
都加上到列表里就好了

输入 [2,4,8,4,0,7,8,9,1,2,4,7,1,7,3] 超时，请优化时间复杂度

zltzlt

阴阳神万物主 发表于 2019-11-9 17:00
但愿不要超过最大递归深度

输入 [35,16,83,87,84,59,48,41,20,54] 超时

塔利班

zltzlt 发表于 2019-11-9 17:02
输入 [2,4,8,4,0,7,8,9,1,2,4,7,1,7,3] 超时，请优化时间复杂度

不是不带0吗。。。。

zltzlt

塔利班 发表于 2019-11-9 17:25
不是不带0吗。。。。

尴尬讲错了，带 0 不带负数

阴阳神万物主

zltzlt 发表于 2019-11-9 17:04
输入 [35,16,83,87,84,59,48,41,20,54] 超时

我请教请教，我这算法，时间复杂度为  O(n!) 没错吧？

zltzlt

阴阳神万物主 发表于 2019-11-9 17:30
我请教请教，我这算法，时间复杂度为  O(n!) 没错吧？

没错。

danteer

1. def func2(list1):
   
2.     global result
   
3.     global trylist
   
4.     trylist = [list1]
   
5.     result = [0]
   
6.     def onetry():
   
7.         global result
   
8.         global trylist
   
9.         trylist2 = []
   
10.         temp2 = []
    
11.         for each in range(len(trylist)):
    
12.             temp = []
    
13.             for i in range(len(trylist[each])):
    
14.                 temp1 = trylist[each][i]
    
15.                 if i > 0:
    
16.                     temp1 *= trylist[each][i-1]
    
17.                 if i < len(trylist[each]) - 1:
    
18.                     temp1 *= trylist[each][i+1]
    
19.                 temp.append(temp1)
    
20.                 if i == 0:
    
21.                     trylist2.append(trylist[each][i+1:])
    
22.                 elif i == len(trylist[each]) - 1:
    
23.                     trylist2.append(trylist[each][:i])
    
24.                 else:
    
25.                     trylist2.append(trylist[each][:i]+trylist[each][i+1:])
    
26.             for dd in temp:
    
27.                 temp2.append(dd+result[each])
    
28.         trylist = trylist2
    
29.         result = temp2
    
30.     while len(trylist[0]) > 1:
    
31.         onetry()
    
32.     for each in range(len(trylist)):
    
33.         result[each] += trylist[each][0]
    
34.     return max(result)

复制代码

零0℃度

不对   删了