优化C#中CanSum动态规划记忆化实现：性能提升与数组替代方案

我正在学习动态规划，跟着FreeCodeCamp的5小时教程（教程用JavaScript编写）。JavaScript里用对象做索引操作很便捷，但在C#里用Dictionary实现记忆化时，需要两次调用ContainsKey，我担心这会影响性能。

初始代码：

public bool CanSum(int n, int[] numbers, Dictionary<int, bool> memo)
{
    if (n == 0) return true;
    if (n < 0) return false;

    if (memo.ContainsKey(n))
        if (memo[n]) return true;

    for (var i = 0; i < numbers.Length; i++)
    {
        var sum = n - numbers[i];

        if (CanSum(sum, numbers, memo))
        {
            if (!memo.ContainsKey(sum))
                memo.Add(sum, true);
            return true;
        }
    }

    return false;
}

请问如何优化这段代码？是否可以使用数组替代Dictionary？

编辑补充：我学到了新写法，能用new() { }初始化空Dictionary，改进后的代码如下：

if (memo.ContainsKey(n))           
     return memo[n];

if (n == 0) return true;
if (n < 0) return false;

for (var i = 0; i < numbers.Length; i++)
{
    var sum = n - numbers[i];

    if (CanSum(sum, numbers, memo))
    {
        memo[n] = true;
        return true;
    }
}

memo[n] = false;

return false;

一、Dictionary的性能优化（避免重复调用ContainsKey） #

你补充的改进代码已经解决了初始版本的核心问题，但还能进一步优化ContainsKey的重复调用——可以用Dictionary.TryGetValue方法，一次调用就能同时完成“检查存在性”和“获取值”的操作，避免两次哈希表查找：

public bool CanSum(int n, int[] numbers, Dictionary<int, bool> memo)
{
    if (memo.TryGetValue(n, out bool result))
        return result;

    if (n == 0) return true;
    if (n < 0) return false;

    foreach (var num in numbers)
    {
        var remainder = n - num;
        if (CanSum(remainder, numbers, memo))
        {
            memo[n] = true;
            return true;
        }
    }

    memo[n] = false;
    return false;
}

TryGetValue方法会直接返回是否找到键，同时把对应的值存入out参数，比先调用ContainsKey再索引取值少一次哈希计算，性能更优。另外把for循环改成foreach也让代码更简洁。

二、用数组替代Dictionary的可行性 #

完全可以用数组替代Dictionary，前提是你能确定n的取值范围是连续的非负整数（比如题目中n是正整数，且最大值明确）。数组的索引访问是O(1)的时间复杂度，比Dictionary的哈希查找更稳定高效。

实现思路 #

1. 初始化一个长度为n+1的可空布尔数组（用null表示未计算，true/false表示计算结果，区分“未计算”和“计算结果为false”的状态）；
2. 用数组索引对应n的值，数组元素存储计算后的结果。

示例代码 #

public bool CanSum(int n, int[] numbers)
{
    bool?[] memo = new bool?[n + 1];
    return CanSumHelper(n, numbers, memo);
}

private bool CanSumHelper(int n, int[] numbers, bool?[] memo)
{
    if (memo[n].HasValue)
        return memo[n].Value;

    if (n == 0) return true;
    if (n < 0) return false;

    foreach (var num in numbers)
    {
        var remainder = n - num;
        if (remainder >= 0 && CanSumHelper(remainder, numbers, memo))
        {
            memo[n] = true;
            return true;
        }
    }

    memo[n] = false;
    return false;
}

数组替代的优劣势 #

• 优势：访问速度更快，无哈希冲突开销；内存布局连续，缓存命中率更高；代码逻辑更直观（针对连续范围的键）。
• 劣势：必须提前知道n的最大值，否则无法确定数组长度；若n取值范围极大但实际用到的键很少，会浪费内存。

三、对补充代码的点评 #

你补充的改进代码已经修正了初始版本的核心问题：

1. 初始版本只缓存了true的结果，未缓存false的结果，会导致重复计算；
2. 改进后会把所有计算过的n值（无论true/false）都存入memo，避免重复递归；
3. 用memo[n] = true/false替代Add方法，简化了代码（C#中Dictionary索引赋值会自动添加不存在的键）。

唯一可优化的点就是用TryGetValue替代ContainsKey+索引取值，进一步提升性能。

内容的提问来源于stack exchange，提问作者I. Eduard