Go语言如何实现静态局部变量解决canSum递归函数记忆化缓存冲突问题

问题根因 #

你当前遇到的问题核心是缓存的作用域不符合预期：

• 包级缓存变量：所有函数调用共享同一份缓存，若不同调用的numbers参数不一致，会直接复用之前的错误计算结果
• 函数内定义缓存：每次递归调用都会重新初始化map，完全失去记忆化的作用

Go语言本身没有类C/C++的函数内静态局部变量，可通过以下方案实现符合要求的记忆化效果。

核心解决方案 #

采用闭包封装对外接口+内部递归的方式实现，核心逻辑是：对外暴露的函数每次初始化独立的缓存，内部递归逻辑通过闭包捕获该缓存实现复用，不同调用之间的缓存完全隔离，不会互相污染。

正确实现代码 #

package main

import "fmt"

func canSum(targetSum int, numbers ...int) bool {
    if targetSum == 0 {
        return true
    }
    if targetSum < 0 {
        return false
    }
    for _, num := range numbers {
        if canSum(targetSum-num, numbers...) {
            return true
        }
    }
    return false
}

func memoCanSum(targetSum int, numbers ...int) bool {
    // 每次对外调用初始化独立缓存，不同调用互不干扰
    memo := map[int]bool{}
    // 内部递归helper，闭包捕获memo和numbers参数
    var helper func(int) bool
    helper = func(curSum int) bool {
        // 优先取缓存结果
        if val, exists := memo[curSum]; exists {
            return val
        }
        if curSum == 0 {
            return true
        }
        if curSum < 0 {
            return false
        }
        for _, num := range numbers {
            if helper(curSum - num) {
                memo[curSum] = true
                return true
            }
        }
        memo[curSum] = false
        return false
    }
    return helper(targetSum)
}

func main() {
    // 非DP实现
    fmt.Println(canSum(21, 2, 4, 8))
    fmt.Println(canSum(80, 2, 4, 8))
    fmt.Println(canSum(300, 7, 14))

    // DP记忆化实现
    fmt.Println(memoCanSum(21, 2, 4, 8))  // 输出 false
    fmt.Println(memoCanSum(80, 2, 4, 8))  // 输出 true
    fmt.Println(memoCanSum(300, 7, 14)) // 输出 false
}

其他可选实现 #

也可以把缓存作为指针参数传递给单独的递归辅助函数，效果和闭包方案一致，仅写法上多一层参数传递：

func memoCanSum2(targetSum int, numbers ...int) bool {
    memo := map[int]bool{}
    return helper(targetSum, numbers, &memo)
}

func helper(curSum int, numbers []int, memo *map[int]bool) bool {
    if val, exists := (*memo)[curSum]; exists {
        return val
    }
    if curSum == 0 {
        return true
    }
    if curSum < 0 {
        return false
    }
    for _, num := range numbers {
        if helper(curSum - num, numbers, memo) {
            (*memo)[curSum] = true
            return true
        }
    }
    (*memo)[curSum] = false
    return false
}

内容的提问来源于stack exchange，提问作者Victor Calixtro