当前位置：首页 > news >正文

Go使用记忆化搜索的套路【以20240121力扣每日一题为例】

news 2025/7/18 6:35:58

题目

在这里插入图片描述

分析

这道题很明显记忆化搜索，用py很容易写出来

Python

class Solution:def splitArray(self, nums: List[int], k: int) -> int:n = len(nums)# 寻找分割子数组中和的最小的最大值s = [0]for num in nums:s.append(s[-1] + num)#print(s)@cachedef dfs(cur, tk): # 前cur个分成tk个的最小的最大值if cur == tk: # 需要保证cur >= tkif cur == 0:return infreturn max(nums[:cur])if tk == 1:return sum(nums[:cur])if tk > cur:return infres = inf # 各自和的最大值的最小值for idx in range(tk - 1, cur):# idx到cur-1为最后一个子数组maxn = dfs(idx, tk - 1)if s[cur] - s[idx] > maxn:maxn = s[cur] - s[idx]if maxn < res:res = maxn#print(cur, tk, res)return resreturn dfs(n, k)

Go

func splitArray(nums []int, k int) int {n := len(nums)// 寻找分割子数组中和的最小的最大值s := make([]int, n+1)for i := 1; i <= n; i++ {s[i] = s[i-1] + nums[i-1]}//fmt.Println(s)// dfs外记忆化type args struct {cur, tk int}memo := map[args]int{} // dfs外记忆化var dfs func(int, int) intdfs = func(cur, tk int) int { // 前cur个分成tk个的最小的最大值if cur == tk { // 需要保证cur >= tkif cur == 0 {return 1<<31 - 1}return max(nums[:cur]...)}if tk == 1 {return sum(nums[:cur]...)}if tk > cur {return 1<<31 - 1}res := 1<<31 - 1 // 各自和的最大值的最小值// dfs内记忆化a := args{cur, tk}if v, ok := memo[a]; ok {return v}defer func() {memo[a] = res} ()// dfs内记忆化for idx := tk - 1; idx < cur; idx++ {// idx到cur-1为最后一个子数组maxn := dfs(idx, tk-1)if s[cur]-s[idx] > maxn {maxn = s[cur] - s[idx]}if maxn < res {res = maxn}}//fmt.Println(cur, tk, res)return res}return dfs(n, k)
}func max(nums ...int) int {res := nums[0]for _, num := range nums {if num > res {res = num}}return res
}func sum(nums ...int) int {res := 0for _, num := range nums {res += num}return res
}