刷题——移动盒子及其相关题目

先看题目

移动盒子

给出一些不同颜色的盒子，盒子的颜色由数字表示，即不同的数字表示不同的颜色。
你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 k 个盒子（k >= 1），这样一轮之后你将得到 k*k 个积分。
当你将所有盒子都去掉之后，求你能获得的最大积分和。
 
示例 1：
输入:
 
[1, 3, 2, 2, 2, 3, 4, 3, 1]
输出:
 
23
解释:
 
[1, 3, 2, 2, 2, 3, 4, 3, 1] 
----> [1, 3, 3, 4, 3, 1] (3*3=9 分) 
----> [1, 3, 3, 3, 1] (1*1=1 分) 
----> [1, 1] (3*3=9 分) 
----> [] (2*2=4 分)
 
提示：盒子的总数 n 不会超过 100。

移除的是相同颜色的连续的k个盒子然后获得积分k*k，k可以等于1，求出最大积分。这道题可以用动态规划的思想来做。

先定义一个三维的列表(n是盒子列表长度)dp=[[[0 for _ in range(n)] for _ in range(n)]]for _ in range(n)

定义dp[i][j][k],是[i , j]区间内能获得最大积分，k表示boxes[i]左边有k个数字与其相等。（这个是重点，如果直接定义二维是解不出来的，必须加上这个条件才能进行状态转移）

如果移除box[i]，得到的积分是 :(1+k)*(1+k)+dp[i+1][j][0]

我们接着考虑，如果在区间[i , j]里如果有boxes[m]与boxes[i]相等时，这个时候：

先计算[i+1 , m-1]这部分的积分，然后再计算[m , j]这部分的积分（此时k要加上1）

积分为：dp[i+1][m-1][0]+dp[m][j][k+1]

我们需要比较这两部分的积分谁更大

采用递归的方式做，贴上代码：

class Solution:
    def removeBoxes(self, boxes):
        n = len(boxes)
        dp = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]
 
        def dfs(i, j, k):
            if i > j:
                return 0
            if dp[i][j][k] > 0:
                return dp[i][j][k]
            # 这里先判断一下，数据可能是一堆相同的数字，我被坑过
            while i < j and boxes[i] == boxes[i + 1]:
                i += 1
                k += 1
            temp = (k + 1) * (k + 1) + dfs(i + 1, j, 0)
            for m in range(i + 1, j + 1):
                if boxes[m] == boxes[i]:
                    temp = max(temp, dfs(i + 1, m - 1, 0) + dfs(m, j, k + 1))
            dp[i][j][k] = temp
            return dp[i][j][k]
 
        return dfs(0, n - 1, 0)
 
 
boxes = [1, 3, 2, 2, 2, 3, 4, 3, 1]
sol = Solution()
res = sol.removeBoxes(boxes)
print(res)

当然了还有两道相似的题目，我们趁热打铁接着看：

戳气球

有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
 
现在要求你戳破所有的气球。每当你戳破一个气球 i 时，你可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。
 
求所能获得硬币的最大数量。
 
说明:
 
你可以假设 nums[-1] = nums[n] = 1，但注意它们不是真实存在的所以并不能被戳破。
0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100
示例:
 
输入: [3,1,5,8]
输出: 167 
解释: nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
     coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

看题目，我们设定nums长度为n+2（也就是首尾各加一个）

先定义一个二维的列表dp=[[0 for _ in range(n+2)] for _ in range(n+2)]

定义dp[i][j],是[i , j]区间打爆所有气球之后能获得最大的金币数，如果区间只有一个数字那就简单了，把左右两边的数字相乘就好了

我们接着考虑，怎么得到转态的转移方程呢？

我们用k去遍历区间[i，j]，假设k是最后被打爆的气球，这个时候我们得到的积分是，三个部分的积分

dp[i][k-1]+dp[k][k]+dp[k+1][j]

如果左右两边的积分已经求得了那就可以做出这道题啦

这里需要注意，不要下意识的觉得dp[k][k]的积分就是nums[k-1]*nums[k]*nums[k+1]！

我们自己定义的dp[i][j]是在区间[i,j]内打爆所有气球之后获得的最大的金币数，也就是说区间dp[i][k-1]和dp[k+1][j]的气球全部被打爆了

所以dp[k][k]的积分为nums[i-1]*nums[k]*nums[j+1]

状态转移方程是

dp[i][j] = max(dp[i][j],dp[i][k-1]+nums[i-1]*nums[k]*nums[j+1]+dp[k+1][j])

上面我们说到了，如果我们能够得到区间之间的积分的话，我们就能够完成这道题目，那我们做的时候先从小区间开始然后慢慢推到大区间~

class Solution:
    def maxCoins(self, nums):
        n = len(nums)
        nums = [1] + nums + [1]
        dp = [[0 for _ in range(n + 2)] for _ in range(n + 2)]
        for t in range(1, n + 1):
            for i in range(1, n - t + 1 + 1):
                j = i + t - 1
                for k in range(i, j + 1):
                    dp[i][j] = max(dp[i][j], dp[i][k - 1] + nums[i - 1] * nums[k] * nums[j + 1] + dp[k + 1][j])
        return dp[1][n]
 
 
nums = [3, 1, 5, 8]
sol = Solution()
print(sol.maxCoins(nums))
        

但是总觉得三重for循环不太对劲，换成递归

class Solution:
    def maxCoins(self, nums):
        n = len(nums)
        nums = [1] + nums + [1]
        dp = [[0 for _ in range(n + 2)] for _ in range(n + 2)]
 
        def dfs(i, j):
            if i > j:
                return 0
            if dp[i][j] > 0:
                return dp[i][j]
            temp = 0
            for k in range(i, j + 1):
                temp = max(temp, dfs(i, k - 1) + nums[i - 1] * nums[k] * nums[j + 1] + dfs(k + 1, j))
            dp[i][j] = temp
            return temp
 
        return dfs(1, n)
 
 
nums = [3, 1, 5, 8]
sol = Solution()
print(sol.maxCoins(nums))

不过最后发现递归的时间花的更多~

奇怪的打印机

有台奇怪的打印机有以下两个特殊要求：
 
打印机每次只能打印同一个字符序列。
每次可以在任意起始和结束位置打印新字符，并且会覆盖掉原来已有的字符。
给定一个只包含小写英文字母的字符串，你的任务是计算这个打印机打印它需要的最少次数。
 
示例 1:
 
输入: "aaabbb"
输出: 2
解释: 首先打印 "aaa" 然后打印 "bbb"。
示例 2:
 
输入: "aba"
输出: 2
解释: 首先打印 "aaa" 然后在第二个位置打印 "b" 覆盖掉原来的字符 'a'。
提示: 输入字符串的长度不会超过 100。

这道题目很有意思，因为一开始不是很懂题目的意思，先注意：一次只能打印同一个字符序列，而且可以从任意的起始位置重新打印字符

先定义一个二维的列表(n是字符串的长度)dp=[[0 for _ in range(n)] for _ in range(n)]

定义dp[i][j],是[i , j]区间实现题目条件最少的打印次数

其实，我们在分析列子的时候可以发现，我们都是要看相同的字符

如果直接去除掉s[i]，那么所需要的次数是1+dp[i+1][j]

接着我们用k去遍历区间[i+1,j]，如果s[i] == s[k]我们就需要考虑了

这个时候根据定义，所需要的最少的次数是：dp[i+1][k-1]+dp[k][j]

所以我们能够得到状态的转移方程是：dp[i][j] = min(dp[i][j],dp[i+1][k-1]+dp[k][j])

那我们还是通过求小区间，然后慢慢变大~

class Solution:
    def strangePrinter(self, s):
        n = len(s)
        if n == 0:
            return 0
        dp = [[0 for _ in range(n)] for _ in range(n)]
        # 从右边往左边推好推一点，真的
        for i in range(n - 1, -1, -1):
            for j in range(i, n):
                if i == j:
                    dp[i][j] = 1
                else:
                    dp[i][j] = 1 + dp[i + 1][j]
                for k in range(i + 1, j + 1):
                    if s[i] == s[k]:
                        dp[i][j] = min(dp[i][j], dp[i + 1][k - 1] + dp[k][j])
        return dp[0][-1]

也可以采用递归的方式做

class Solution:
    def strangePrinter(self, s):
        n = len(s)
        if n == 0:
            return 0
        dp = [[0 for _ in range(n)] for _ in range(n)]
 
        def dfs(i, j):
            if i > j:
                return 0
            if dp[i][j] > 0:
                return dp[i][j]
            temp = 1 + dfs(i + 1, j)
            for k in range(i + 1, j + 1):
                if s[i] == s[k]:
                    temp = min(temp, dfs(i + 1, k - 1) + dfs(k, j))
            dp[i][j] = temp
            return temp
 
        return dfs(0, n - 1)

解题思路大概就是定义几维的列表，定义代表什么，然后再通过逻辑关系得到状态转移方程（吼吼，说得容易），用递归的话逻辑关系看的更加清楚一点~（码了一天的字了，呜呜呜）