见路不走

V1

2022/11/03阅读:15主题:红绯

打爆气球

【每日一题】打爆气球

给定一个数组 arr,代表一排有分数的气球。每打爆一个气球都能获得分数,假设打爆气球的分数为 X,获得分数的规则如下:

  1. 如果被打爆气球的左边有没打爆的气球,找到离被打爆气球最近的气球,假设分数为 L;如果被打爆气球的右边有没有打爆的气球,找到离被打爆气球最近的气球,假设分数为 R。获得分数为 L * X * R
  2. 如果被打爆气球的左边有没打爆的气球,找到离被打爆气球最近的气球,假设分数为 L;如果被打爆气球的右边所有气球都已经被打爆。获得分数为:L*X
  3. 如果被打爆气球的左边所有气球都已经被打爆;如果被打爆气球的右边有没有打爆的气球,找到离被打爆气球最近的气球,假设分数为 R。获得分数为:R*X
  4. 如果被打爆气球的左边和右边所有气球都已经被打爆。获得分数为: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)都已经被打爆了,所以

同理:

对于中间下边比如:下标 2 最后被打爆,那么其他气球已经被打爆(1,3,4,5,6),气球 1 被打爆:f(1,1) 和 气球 3,4,5,6 被打爆表示为 f(3,6) 。因此

总结:此方案只需要两个参数,在改动态规划时,需要一张二维表。此方案比较优秀。

def max_score1(arr):
    if not arr: return 0
    # 哨兵,因为 f 要求 arr[l-1] 和 arr[r+1] 一定没有被打破
    arr.insert(01)
    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

总结:

  1. 大问题所有的影响都要通过参数传递给小问题,便于小问题在决策过程中使用。
  2. 可能性尝试策略:递归函数参数越少越好,参数简单越好。

解法二:动态规划

如下图: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(01)
    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) - 30-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")

分类:

后端

标签:

后端

作者介绍

见路不走
V1