Daily LeetCode – day0146 1799. Maximize Score After N Operations

// 1799. Maximize Score After N Operations
class Solution {
    public int maxScore(int[] nums) {
        int len = nums.length;
        int[] memo = new int[1 << len];
        return helper(nums, len, 1, 0, memo);
    }

    private int helper(int[] nums, int len, int operations, int mask, int[] memo) {
        if (operations > (len / 2)) return 0;
        if (memo[mask] != 0) return memo[mask];
        int ret = 0;
        for (int i = 0; i < len; ++i) {
            if ((mask & (1 << i)) != 0) continue;
            for (int j = i + 1; j < len; ++j) {
                if ((mask & (1 << j)) != 0) continue;
                int newMask = mask | (1 << i) | (1 << j);
                int score = operations * gcd(nums[i], nums[j]);
                ret = Math.max(ret, score + helper(nums, len, operations + 1, newMask, memo));
            }
        }
        memo[mask] = ret;
        return ret;
    }

    private int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
}
学习笔记:
这是一道苦难的题目,用到了动态规划或者记忆化搜索,还有状态压缩位运算实现。
8个数字尝试两两进行配对,那就算是记忆化搜索,也还是得用动态规划的思想来反向递推。
这道题做起来很困难,所以以后有空还是得回顾。


关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录。将固定链接加入收藏夹。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注