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

题目

在这里插入图片描述

分析

这道题很明显记忆化搜索，用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)
        
        @cache
        def dfs(cur, tk): # 前cur个分成tk个的最小的最大值
            if cur == tk: # 需要保证cur >= tk
                if cur == 0:
                    return inf
                return max(nums[:cur])
            if tk == 1:
                return sum(nums[:cur])
            if tk > cur:
                return inf
            res = 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 res

            
        
        return 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) int
    dfs = func(cur, tk int) int { // 前cur个分成tk个的最小的最大值
        if cur == tk { // 需要保证cur >= tk
            if 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 := 0
    for _, num := range nums {
        res += num
    }
    return res
}