力扣3366.最小数组和

力扣3366.最小数组和

题目

题目解析及思路

题目要求对于数组进行两种操作，使最终数组和最小

注意：每个元素可以同时执行两种操作

考虑动归，暴力的遍历每种情况

代码

• 记忆化搜索

class Solution {
public:
    // minArraySum 函数用于计算在执行任意次数的操作后，nums 中所有元素的最小可能和
    int minArraySum(vector<int>& nums, int k, int op1, int op2) {
        int n = nums.size(); // 数组的大小
        // memo 用来缓存递归计算结果，memo[i][op1][op2] 表示在 nums[i] 这个位置时，剩余 op1 次减半操作和 op2 次减去 k 操作的最小和
        vector<vector<vector<int>>> memo(n, vector<vector<int>>(op1 + 1, vector<int>(op2 + 1, -1)));

        // 定义深度优先搜索 (DFS) 函数来递归计算最小可能和
        auto dfs = [&](auto&& dfs, int i, int op1, int op2) -> int {
            // 递归终止条件：当 i < 0 时，表示已经处理完所有元素，返回 0
            if (i < 0) {
                return 0;
            }

            // 通过引用获取 memo[i][op1][op2] 的值
            int &res = memo[i][op1][op2];
            int x = nums[i]; // 当前元素的值
            
            // 如果该状态已经计算过，直接返回缓存的结果
            if (res != -1) {
                return res;
            }

            // 初始化当前状态的结果为：不进行任何操作，直接将当前元素加到总和中
            res = dfs(dfs, i - 1, op1, op2) + x;

            // 操作 1：如果还有剩余的减半操作 (op1 > 0)，尝试对当前元素进行减半并向上取整
            if (op1) {
                res = min(res, dfs(dfs, i - 1, op1 - 1, op2) + (x + 1) / 2);
            }

            // 操作 2：如果还有剩余的减去 k 操作 (op2 > 0)，并且当前元素大于等于 k，尝试进行减去 k 操作
            if (op2 && x >= k) {
                res = min(res, dfs(dfs, i - 1, op1, op2 - 1) + x - k);
                
                // 如果 op1 还有剩余，并且可以同时进行减半和减去 k 操作，尝试这种组合
                if (op1) {
                    int y = (x + 1) / 2 >= k ? (x + 1) / 2 - k : (x - k + 1) / 2;
                    res = min(res, dfs(dfs, i - 1, op1 - 1, op2 - 1) + y);
                }
            }

            // 返回当前状态的最小可能和
            return res;
        };

        // 调用 dfs 函数从数组的最后一个元素开始进行递归，初始时的操作次数分别为 op1 和 op2
        return dfs(dfs, n - 1, op1, op2);
    }
};

• 递推

class Solution {
public:
    // minArraySum 函数用于计算执行操作后的最小可能和
    int minArraySum(vector<int>& nums, int k, int op1, int op2) {
        int n = nums.size(); // 获取 nums 数组的大小
        
        // 创建动态规划表 f，其中 f[i][p][q] 表示前 i 个元素，使用 p 次减半操作和 q 次减去 k 操作后的最小和
        // 这里的 i+1, p+1, q+1 是为了方便计算，防止访问越界
        vector<vector<vector<int>>> f(n + 1, vector<vector<int>>(op1 + 1, vector<int>(op2 + 1, 0)));
        
        // 遍历所有元素
        for (int i = 0; i < n; i++) {
            int x = nums[i]; // 当前处理的元素值
            
            // 遍历操作次数 op1 和 op2
            for (int p = 0; p <= op1; p++) {
                for (int q = 0; q <= op2; q++) {
                    // 当前状态的初始结果：不做任何操作，仅将当前元素加入和中
                    int res = f[i][p][q] + x;

                    // 操作 1：如果还有剩余的减半操作 (p > 0)，尝试对当前元素进行减半
                    if (p) {
                        res = min(res, f[i][p - 1][q] + (x + 1) / 2);  // 向上取整
                    }

                    // 操作 2：如果还有剩余的减去 k 操作 (q > 0)，并且当前元素大于等于 k，尝试从当前元素减去 k
                    if (q && x >= k) {
                        res = min(res, f[i][p][q - 1] + x - k);  // 减去 k

                        // 如果还有剩余的减半操作 (p > 0)，同时进行减半和减去 k 的组合操作
                        if (p) {
                            // 计算当前元素减半后的值是否大于等于 k，并做相应的调整
                            int y = (x + 1) / 2 >= k ? (x + 1) / 2 - k : (x - k + 1) / 2;
                            res = min(res, f[i][p - 1][q - 1] + y);  // 同时减半和减去 k
                        }
                    }

                    // 更新 f[i+1][p][q]，即考虑当前元素后的最小和
                    f[i + 1][p][q] = res;
                }
            }
        }

        // 返回最终的结果，考虑所有元素并使用最多 op1 次减半操作和 op2 次减去 k 操作
        return f[n][op1][op2];
    }
};