2024-12-02：划分数组得到最小的值之和。用go语言，你有两个数组，nums 和 andValues，它们的长度分别为 n 和 m。定义数组的“值”为其最后一个元素。
你的任务是将 nums 划分为 m 个不重叠的连续子数组。对于第 i 个子数组 [li, ri]，该子数组的所有元素通过按位与运算后，结果必须等于 andValues[i]。换句话说，对于所有的 1 <= i <= m，应该满足 nums[li] & nums[li + 1] & … & nums[ri] == andValues[i]，其中 & 表示按位与运算符。
你的目标是返回将 nums 划分为 m 个子数组时，得到的可能的最小子数组值之和。如果无法完成这样的划分，则返回 -1。
提示：
1 <= n == nums.length <= 10000。
1 <= m == andValues.length <= min(n, 10)。
1 <= nums[i] < 100000。
0 <= andValues[j] < 100000。
输入： nums = [1,4,3,3,2], andValues = [0,3,3,2]。
输出： 12。
解释：
唯一可能的划分方法为：
1.[1,4] 因为 1 & 4 == 0；
2.[3] 因为单元素子数组的按位 AND 结果就是该元素本身；
3.[3] 因为单元素子数组的按位 AND 结果就是该元素本身；
4.[2] 因为单元素子数组的按位 AND 结果就是该元素本身。
这些子数组的值之和为 4 + 3 + 3 + 2 = 12。
答案2024-12-02：
题目来自leetcode3117。
大体步骤如下：
1.定义常量 INF 作为无穷大的表示，为 (1 << 20) - 1。
2.初始化 nums 和 andValues 的长度 n 和 m。
3.创建 memo 数组，大小为 n*m，用于记忆化搜索过程中的中间结果。
4.定义递归函数 dfs(i, j, cur int) int，用于计算最小子数组值之和，函数体如下：
-
计算当前状态的键值 key 以在 memo 中保存中间结果。
-
检查结束条件：如果 i 和 j 都达到末尾则返回 0，如果其中一个到达末尾则返回 INF。
-
检查 memo 中是否已有当前状态结果，若有则直接返回。
-
对当前的 cur 进行按位与操作并检查是否符合条件，若不符合则返回 INF。
-
递归调用 dfs 处理两种情况：不选当前元素和选取当前元素。
-
更新 memo 并返回结果。
5.调用 dfs(0, 0, INF) 启动递归计算最小值之和，并将结果存储在 res 中。
6.检查 res 是否小于INF，如果是则返回 res，否则返回 -1。
总的时间复杂度为 O(n*m)。
总的额外空间复杂度为 O(n*m)。
Go完整代码如下：
package main
import (
"fmt"
)
func minimumValueSum(nums []int, andValues []int) int {
const INF = (1 << 20) - 1
n := len(nums)
m := len(andValues)
memo := make([]map[int]int, n*m)
for i := range memo {
memo[i] = make(map[int]int)
}
var dfs func(i, j, cur int) int
dfs = func(i, j, cur int) int {
key := i*m + j
if i == n && j == m {
return 0
}
if i == n || j == m {
return INF
}
if val, ok := memo[key][cur]; ok {
return val
}
cur &= nums[i]
if cur&andValues[j] < andValues[j] {
return INF
}
res := dfs(i+1, j, cur)
if cur == andValues[j] {
res = min(res, dfs(i+1, j+1, INF)+nums[i])
}
memo[key][cur] = res
return res
}
res := dfs(0, 0, INF)
if res < INF {
return res
}
return -1
}
func main() {
nums := []int{1, 4, 3, 3, 2}
andValues := []int{0, 3, 3, 2}
fmt.Println(minimumValueSum(nums, andValues))
}
Rust完整代码如下：
use std::collections::HashMap;
const INF: i32 = (1 << 20) - 1;
fn minimum_value_sum(nums: &[i32], and_values: &[i32]) -> i32 {
let n = nums.len();
let m = and_values.len();
let mut memo = vec![HashMap::new(); n * m];
fn dfs(
i: usize,
j: usize,
cur: i32,
nums: &[i32],
and_values: &[i32],
memo: &mut Vec<HashMap<i32, i32>>,
) -> i32 {
if i == nums.len() && j == and_values.len() {
return 0;
}
if i == nums.len() || j == and_values.len() {
return INF;
}
let key = i * and_values.len() + j;
if let Some(&val) = memo[key].get(&cur) {
return val;
}
let new_cur = cur & nums[i];
if new_cur & and_values[j] < and_values[j] {
return INF;
}
let mut res = dfs(i + 1, j, new_cur, nums, and_values, memo);
if new_cur == and_values[j] {
res = res.min(dfs(i + 1, j + 1, INF, nums, and_values, memo) + nums[i]);
}
memo[key].insert(cur, res);
res
}
let res = dfs(0, 0, INF, nums, and_values, &mut memo);
if res < INF {
res
} else {
-1
}
}
fn main() {
let nums = vec![1, 4, 3, 3, 2];
let and_values = vec![0, 3, 3, 2];
println!("{}", minimum_value_sum(&nums, &and_values));
}
