11981. 最小化目标值与所选元素的差

难度中等15 收藏 分享 切换为英文 接收动态 反馈
给你一个大小为 m x n 的整数矩阵 mat 和一个整数 target 。
从矩阵的 每一行 中选择一个整数，你的目标是 最小化 所有选中元素之 和 与目标值 target 的 绝对差 。
返回 最小的绝对差 。
a 和 b 两数字的 绝对差 是 a - b 的绝对值。

记忆化搜索乃竞赛选手基本技能

我的解（超时）

• 想法是O(N^3)的贪心寻找一个局部最优解，做剪枝标准
• 再使用回溯法O(N^3)，辅以剪枝，以优化时间复杂度

class Solution:
    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:
        min_=[math.inf]
        m,n=len(mat),len(mat[0])
        #isvisited=[False]*m
        #必须使用记忆化搜索，或者使用动态规划
        #动态具有最优化准则
        #使用贪心+剪枝
        dp=[[math.inf]*n for _ in range(m)]
        for i in range(n):
            dp[0][i]=target-mat[0][i]
        for i in range(1,m):
            for j in range(n):
                for jj in range(n):
                    dp[i][j]=dp[i-1][jj]-mat[i][j] if abs(dp[i][j])>abs(dp[i-1][jj]-mat[i][j]) \
                        else dp[i][j]
        min_[0]=min([abs(i) for i in dp[-1]])
        #print(min_[0])
        def dfs(sum_,i):
            if i>=m:
                min_[0]=min(min_[0],abs(target-sum_))
                return 
            for j in range(n):
                try:
                    if sum_+mat[i][j]-target>min_[0]:
                        continue
                    #剪枝也不行
                    dfs(sum_+mat[i][j],i+1)
                except:
                    print(i,j)
        dfs(0,0)
        return min_[0]

• 竞赛难度之一：每个题的数种解法，没有一个看懂的，易放弃
• 使用模拟不同的加和，可能由于set的去重效果使得时间复杂度较低

class Solution:
    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:
        f=set([0])
        m,n=len(mat),len(mat[0])
        for i in range(m):
            g=set()
            for j in f:
                for jj in mat[i]:
                    g.add(j+jj)
            f=g
        ans=math.inf
        for i in f:
            ans=min(ans,abs(i-target))
        return ans
            

*剪枝方案，加和大于target时记录最小的大于target的值，加和小于target时，向set里更新，最后只需要在大于target的最小值与target的差值，与集合与target差值的最小值比较即可。

该题不需要记录求解路径，故不需要搜索算法，而是使用动态规划，结合移位运算，加和可以使用位置表示，加x相当于1左移x

class Solution:
    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:
        def to_binary_reversed(x):
            ans=''
            while x:
                ans+=str(x%2)
                x//=2
            return ans
        m,n=len(mat),len(mat[0])
        f=[0]*m
        for j in range(n):
            f[0]|=1<<mat[0][j]
        for i in range(1,m):
            for j in range(n):
                f[i]|=f[i-1]<<mat[i][j]
        move=to_binary_reversed(f[-1])
        ans=math.inf
        for i in range(len(move)):
            if move[i]=='1':
                ans=min(ans,abs(i-target))
        return ans

image.png

• 数学知识解题之：相加为某固定数，那么这些数当相等时乘积最大，当这些数尽可能平均分散在两侧时成绩最小。

• 由上面的定理可知，当sum=p时，该（sum/n）^n乘积最大，如何最大化该表达式，通过求导以及代数得，sum/n=e时最大，带入整数2，3。得sum/n=3时，乘积最大，即三等时最大。

待补题与代码