b_lc_ 最小化目标值与所选元素的差（dp / bitset 优化内存）

本文主要是介绍b_lc_ 最小化目标值与所选元素的差（dp / bitset 优化内存），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

m x n 的整数矩阵 mat 和一个整数 target 。从矩阵的 每一行 中选择一个整数，你的目标是 最小化 所有选中元素之 和 与目标值 target 的 绝对差 。返回 最小的绝对差 。

思路：朴素 dp

const int N = 70;
const int MAX_S = N * N;
class Solution {
public:
    bool f[N][MAX_S + 1]; //第i行，和为j是否可能
    int minimizeTheDifference(vector<vector<int>>& g, int tar) {
        int n = g.size(), m = g[0].size();
        for (int j = 0; j < m; j++) {
            f[0][g[0][j]] = true;
        }
        for (int i = 1; i < n; i++) {
            for (int s = 0; s <= MAX_S; s++) {
                if (!f[i-1][s]) {
                    continue;
                }
                for (int j = 0; j < m; j++) {
                    if (s + g[i][j] > MAX_S) {
                        continue;
                    }
                    f[i][s + g[i][j]] = true; 
                }
            }
        }
        int ans = INT_MAX;
        for (int s = 0; s <= MAX_S; s++) {
            if (f[n-1][s]) {
                ans = min(ans, abs(s-tar));
            }
        }
        return ans;
    }
};

MAX_S 大一点就超时了。
优化：可以用 bitset 来压缩内存

class Solution {
public:
    int minimizeTheDifference(vector<vector<int>>& A, int target) {
        int n=A.size();
        int m=A[0].size();
        bitset<5000> F[n];
        F[0]=0;
        for (int i=0;i<m;++i) F[0][A[0][i]]=1;
        for (int i=1;i<n;++i)
        {
            F[i]=0;
            for (int j=0;j<m;++j)
                F[i]|=F[i-1]<<A[i][j];
        }
        int ans=4900;
        for (int i=1;i<=4900;++i)
            if (F[n-1][i])
                ans=min(ans,abs(target-i));
        return ans;
    }
};

二维优化成一维：利用滚动数组

这篇关于b_lc_ 最小化目标值与所选元素的差（dp / bitset 优化内存）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！