Jianbo Dai's

lc1049.最后一块石头的重量II

 
  • Dec 05, 2020

题目链接

啊啊啊看到题就知道应该是用动态规划，但是具体怎么做好像没什么思路。然后点开题解，就看到其实可以转换成”将石头分成两堆，不断缩小两堆石头重量的差值，最小差值即为最小剩余重量“，机智啊，这就转换成01背包问题了啊。 哦不过我又忘了01背包咋做了，虽然参考之前的“分割等和子集”写出来了但是好像不知道怎么把得到的结果转化成答案…哦发现错误了，原来是因为我的最大重量是上取整的，改成下取整就对了。这个算法的时间复杂度是O（N），空间复杂度是O（NM）。然后实现2是优化了空间之后的，空间复杂度给减少到了O（N）。

class Solution:
    def lastStoneWeightII1(self, stones: List[int]) -> int:
        if not stones:
            return 0
        row = len(stones)
        col = sum(stones) // 2
        dp = [[False]*(col+1) for x in range(row)]
        if stones[0] <= col:
            dp[0][stones[0]] = True
        for i in range(1, row):
            for j in range(col+1):
                dp[i][j] = dp[i-1][j]
                if stones[i] == j:
                    dp[i][j] = True
                if stones[i] < j:
                    dp[i][j] = dp[i-1][j] or dp[i-1][j-stones[i]]
        for k in range(len(dp[-1])-1, -1, -1):
            if dp[-1][k] == True:
                break
        return sum(stones) - k * 2

    def lastStoneWeightII2(self, stones: List[int]) -> int:
        if not stones:
            return 0
        n = len(stones)
        s = sum(stones)
        dp = [0]*(s//2+1)
        for i in range(n):
            for j in range(s//2, stones[i]-1, -1):
                dp[j] = max(dp[j], dp[j-stones[i]]+stones[i])
        return s - 2*dp[-1]
Search