关于程序员:每日一题打爆气球

36次阅读

共计 2986 个字符，预计需要花费 8 分钟才能阅读完成。

给定一个数组 arr，代表一排有分数的气球。每打爆一个气球都能取得分数，假如打爆气球的分数为 X，取得分数的规定如下：

如果被打爆气球的右边有没打爆的气球，找到离被打爆气球最近的气球，假如分数为 L；如果被打爆气球的左边有没有打爆的气球，找到离被打爆气球最近的气球，假如分数为 R。取得分数为 L X R

如果被打爆气球的右边有没打爆的气球，找到离被打爆气球最近的气球，假如分数为 L；如果被打爆气球的左边所有气球都曾经被打爆。取得分数为：L*X

如果被打爆气球的右边所有气球都曾经被打爆；如果被打爆气球的左边有没有打爆的气球，找到离被打爆气球最近的气球，假如分数为 R。取得分数为：R*X

如果被打爆气球的右边和左边所有气球都曾经被打爆。取得分数为：X

指标是打爆所有气球，返回能取得的最大分数。

【举例】

arr =【3,2,5】

如果先打爆 3，取得 3*2；再打爆 2，取得 2* 5 ; 最初打爆 5，取得 5；总分为：6+10+5=21.

如果先打爆 3，取得 3*2；再打爆 5，取得 2* 5 ; 最初打爆 2，取得 2；总分为：6+10+2=18.

如果先打爆 2，取得 3*2*5；再打爆 3，取得 3* 5 ; 最初打爆 5，取得 5；总分为：30+15+5=50.

如果先打爆 2，取得 3*2*5；再打爆 5，取得 3* 5 ; 最初打爆 3，取得 3；总分为：30+15+3=48.

如果先打爆 5，取得 2*5；再打爆 3，取得 3* 2 ; 最初打爆 2，取得 2；总分为：10+6+2=18.

如果先打爆 5，取得 2*5；再打爆 2，取得 3* 2 ; 最初打爆 3，取得 3；总分为：10+6+3=19.

返回最大分数为 50

本题练习：尝试计划抉择技巧 。

解法一：暴力递归

可能性剖析：

范畴尝试模型。

尝试计划一

尝试每一个地位的气球 优先 被打爆。

例如：下图先打爆下标为 2 的气球，那么右边的子过程是：f(0, 1)。因为下标为 2 的气球曾经被打爆，因而 f(0,1) 无奈确定左边没有打爆最近的气球。同理 f(3, 4) 无奈确定右边没有打爆最近的气球。

因而须要其余参数来供子问题决策。f(left , right, left_score, right_score)，left_score 示意右边没有打爆的最近气球。right_score 示意左边有没有打爆的最近气球。

f 有四个变量，在改动静布局时，须要一张四维表，并且这张四维表的大小受限于 arr 中数值的大小。

论断：这种尝试模型不够好。

尝试计划二

尝试每一个地位的气球 最初 被打爆。

f(L , R) 示意打爆 arr[L…R] 上所有的气球。

潜台词：L – 1 和 R + 1 的气球肯定没有被打爆。

如下图：f(1, 6) 须要将下标从 1 到 6 的气球逐个尝试最初打爆。两个端点 1 和 6 计算比拟非凡，独自计算一下。

f(1,1) 示意下标 1 最初被打爆，那么其余气球（2,3,4,5,6）都曾经被打爆了，所以 $f(1,1)=arr[0]*arr[1]*arr[7]$

同理：$f(1,1)=arr[0]*arr[6]*arr[7]$

对于两头下边比方：下标 2 最初被打爆，那么其余气球曾经被打爆（1,3,4,5,6）, 气球 1 被打爆：f(1,1) 和气球 3,4,5,6 被打爆示意为 f(3,6)。因而 $f(1,6)=f(1,1)+f(3,6)+arr[0]*arr[2]*arr[7]$

总结：此计划只须要两个参数，在改动静布局时，须要一张二维表。此计划比拟优良。

def max_score1(arr):
    if not arr: return 0
    # 哨兵，因为 f 要求 arr[l-1] 和 arr[r+1] 肯定没有被突破
    arr.insert(0, 1)
    arr.append(1)
    return f1(arr, 1, len(arr) - 2)

# 打爆 arr[l...r] 范畴上的所有气球，返回最大的分数
# 假如 arr[l-1] 和 arr[r+1] 肯定没有被突破
def f1(arr, l, r):
    # 如果 arr[l...r] 范畴上只有一个气球，间接打爆即可
    if l == r:
        return arr[l - 1] * arr[l] * arr[r + 1]

    # 最初打爆 arr[l] 的计划 和 最初打爆 arr[r] 的计划，先比拟一下
    res = max(arr[l - 1] * arr[l] * arr[r + 1] + f(arr, l + 1, r),
              arr[l - 1] * arr[r] * arr[r + 1] + f(arr, l, r - 1))

    # 尝试两头地位的气球最初打爆的每一种计划
    for k in range(l + 1, r):
        res = max(res, arr[l - 1] * arr[k] * arr[r + 1] + f(arr, l, k - 1) + f(arr, k + 1, r))

    return res

总结：

大问题所有的影响都要通过参数传递给小问题，便于小问题在决策过程中应用。
可能性尝试策略：递归函数参数越少越好，参数简略越好。

解法二：动静布局

如下图：f(1, 6) 依赖 f(2 ,6), f(3,6), f(4,6), f(5,6), f(6,6), f(1 ,5), f(1,4), f(1,3), f(1,2)

def max_score2(arr):
    if not arr: return 0
    arr.insert(0, 1)
    arr.append(1)
    dp = [[0] * (len(arr)) for _ in range(len(arr))]
    for i in range(1, len(arr) - 1):
        dp[i][i] = arr[i - 1] * arr[i] * arr[i + 1]

    for l in range(len(arr) - 3, 0, -1):
        for r in range(l + 1, len(arr) - 1):
            res = max(arr[l - 1] * arr[l] * arr[r + 1] + f(arr, l + 1, r),
                      arr[l - 1] * arr[r] * arr[r + 1] + f(arr, l, r - 1))
            for k in range(l + 1, r):
                res = max(res, arr[l - 1] * arr[k] * arr[r + 1] + f(arr, l, k - 1) + f(arr, k + 1, r))
        dp[l][r] = res

    return dp[1][len(arr) - 2]

对数器：

import random

def generator_random_arr(max_size, max_value):
    return [item for item in
            set([int(random.random() * max_value) + 1 for _ in range(int(random.random() * max_size) + 1)])]

def check():
    global map
    max_size = 5
    max_value = 10
    for _ in range(10000):
        arr = generator_random_arr(max_size, max_value)
        # print("info2", aim, arr)
        res = max_score(arr[:])
        res2 = max_score2(arr[:])
        # print("Info", "res=", res, "res2=", res2, aim, arr)
        if res != res2 or res != res2:
            print("ERROR", "res=", res, "res2=", res2, arr)
    print("OVER")

本文由 mdnice 多平台公布

正文完