[已解决]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

"""
我的理解：
                                 l-----m-----r
                                 |     |     |
nums: [3, 1, 5, 8] -> new_nums: [1, 3, 1, 5, 8, 1]

对于上方 new_nums 这种情况
=> dp[l][r] = dp[l][m] + dp[m][r] + new_nums[l] * new_nums[m] * new_nums[r]
   dp[l][r]: 吹爆 l 与 r 之间的气球，但不包括 l 和 r；不同的 m 可能有不同的 dp[l][r]
"""
def f271(nums):
    new = [1] + [i for i in nums if i] + [1]    # 删去对结果没有影响的 0，并补齐两侧默认的 1
    n = len(new)
    dp = [[0]*n for _ in range(n)]
    for gap in range(2, n):                     # 从 3 个一组，到 n 个一组
        for l in range(n - gap):
            r = l + gap
            tmp = new[l] * new[r]               # 避免重复计算
            for m in range(l + 1, r):
                dp[l][r] = max(dp[l][r], dp[l][m] + dp[m][r] + tmp * new[m])
    return dp[0][-1]

跳转到最佳答案楼层

华一仙

"""
我的理解：
                                 l-----m-----r
                                 |     |     |
nums: [3, 1, 5, 8] -> new_nums: [1, 3, 1, 5, 8, 1]

对于上方 new_nums 这种情况
=> dp[l][r] = dp[l][m] + dp[m][r] + new_nums[l] * new_nums[m] * new_nums[r]
   dp[l][r]: 吹爆 l 与 r 之间的气球，但不包括 l 和 r；不同的 m 可能有不同的 dp[l][r]
"""
def f271(nums):
    new = [1] + [i for i in nums if i] + [1]    # 删去对结果没有影响的 0，并补齐两侧默认的 1
    n = len(new)
    dp = [[0]*n for _ in range(n)]
    for gap in range(2, n):                     # 从 3 个一组，到 n 个一组
        for l in range(n - gap):
            r = l + gap
            tmp = new[l] * new[r]               # 避免重复计算
            for m in range(l + 1, r):
                dp[l][r] = max(dp[l][r], dp[l][m] + dp[m][r] + tmp * new[m])
    return dp[0][-1]

阴阳神万物主

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

zltzlt

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

阴阳神万物主

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

塔利班

还有0分负分这种坑么

zltzlt

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

没有负分 ，但是有 0 分

WXF666

捏爆哪个才能最大呢。。

塔利班

def ball(X):
    results=[]
    def f(X,lastsum):
        if len(X)==1:
            return X[0]
        elif len(X)==2:
            return lastsum+X[0]*X[1]+max(X)
        else:
            for i in range(1,len(X)-1):
                temp=X[:]
                # print(i,len(X))
                mul=X[i]*X[i-1]*X[i+1]
                temp.pop(i)
                results.append(f(temp,mul+lastsum))
    f(X,0)
    return max([e for e in results if e])

print(ball([3,1,5]))
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

都加上到列表里就好了

def ball(X):
    results=[]
    def f(X,lastsum):
        if len(X)==1:
            results.append(X[0])
        elif len(X)==2:
            results.append(lastsum+X[0]*X[1]+max(X))
        else:
            for i in range(1,len(X)-1):
                temp=X[:]
                mul=X[i]*X[i-1]*X[i+1]
                temp.pop(i)
                f(temp,mul+lastsum)
    f(X,0)
    return max(results)

print(ball([3,1,5]))
print(ball([4, 1, 5, 10]))
print(ball([10]))

阴阳神万物主

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

def solve(nums:'至少有一个元素的整数数组',tot:'int 基础分数'=0)->'int 最多分数':
    le = len(nums)
    res = tot
    #print('调试',nums,tot)
    for j in range(le):
        mul = nums[j]
        if j > 0:
            mul *= nums[j-1]
        if j < le-1:
            mul *= nums[j+1]
        tot += mul
        #print('调试 吹爆',nums[j])
        get = solve(nums[:j]+nums[j+1:],tot)
        if get > res:
            res = get
        tot -= mul
        #print('调试 恢复',nums[j])
    return res

if __name__ == '__main__':
    print('示例1 270 输出：',solve([4,1,5,10]))
    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

def func2(list1):
    global result
    global trylist
    trylist = [list1]
    result = [0]
    def onetry():
        global result
        global trylist
        trylist2 = []
        temp2 = []
        for each in range(len(trylist)):
            temp = []
            for i in range(len(trylist[each])):
                temp1 = trylist[each][i]
                if i > 0:
                    temp1 *= trylist[each][i-1]
                if i < len(trylist[each]) - 1:
                    temp1 *= trylist[each][i+1]
                temp.append(temp1)
                if i == 0:
                    trylist2.append(trylist[each][i+1:])
                elif i == len(trylist[each]) - 1:
                    trylist2.append(trylist[each][:i])
                else:
                    trylist2.append(trylist[each][:i]+trylist[each][i+1:])
            for dd in temp:
                temp2.append(dd+result[each])
        trylist = trylist2
        result = temp2
    while len(trylist[0]) > 1:
        onetry()
    for each in range(len(trylist)):
        result[each] += trylist[each][0]
    return max(result)

零0℃度

不对   删了