[对数据分析,人工智能,金融科技,风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章]
1 <= n <= 7nums.length == 2 * n1 <= nums[i] <= 1e6 示例 1: 输入:nums = [1,2] 输出:1 解释:最优操作是: (1 * gcd(1, 2)) = 1示例 2: 输入:nums = [3,4,6,8] 输出:11 解释:最优操作是: (1 * gcd(3, 6)) + (2 * gcd(4, 8)) = 3 + 8 = 11示例 3: 输入:nums = [1,2,3,4,5,6] 输出:14 解释:最优操作是: (1 * gcd(1, 5)) + (2 * gcd(2, 4)) + (3 * gcd(3, 6)) = 1 + 4 + 9 = 14题解算法:状态压缩DP一共有 2n 个数,每次从中取出 2 个数,共取 n 次.从动态规划的角度看的话,阶段是比较容易确定的,就是每次取数就是一个阶段,共 n 个阶段.
每次取数后,nums 中剩余的数构成了下一个阶段的子问题.这个子问题的答案受到 nums 中剩余的数的情况的影响,因此状态应该 nums 中的数字是否被取出.
按照前面的分析,可以定义 dp[i][s] 为第 i 次取数时,nums 中剩余的数的状态为 s 的情况下的最终的最大分数和.
但注意,由于每一阶段剩余数字个数减 2,而 s 中隐含了数字的个数,因此 i 可以省略掉.