C++递归问题：求解SPOJ COINS题目时类变量值丢失

你遇到的核心问题是类的成员变量会被所有递归调用共享——每次递归recur函数时，都会修改同一个实例的b、c、d、x，上层递归的数值还没来得及使用就被下层覆盖了，自然会丢失原有值。

第一步：用局部变量替代成员变量 #

把这些变量从类成员移到recur函数内部，让每次递归调用都拥有独立的变量副本，就不会互相干扰了。修改后的基础递归代码如下：

#include<iostream>
using namespace std;

class a {
public:
    int recur(int n) {
        // 用局部变量代替类成员，每个递归调用都有自己的变量
        int b = n / 2;
        if (b >= 12) {
            b = recur(b);
        }
        int c = n / 3;
        if (c >= 12) {
            c = recur(c);
        }
        int d = n / 4;
        if (d >= 12) {
            d = recur(d);
        }
        int x = b + c + d;
        // 注意：这里还要比较x和n本身，因为有时候直接拿n比拆分更划算（比如n<12时）
        return max(x, n);
    }
};

int main() {
    a obj;
    int n;
    while (cin >> n) {
        cout << obj.recur(n) << endl;
    }
    return 0;
}

第二步：优化性能——添加记忆化（避免重复计算） #

单纯递归虽然解决了变量覆盖问题，但对于SPOJ的测试用例来说会超时，因为很多数值会被重复计算多次（比如计算100时会用到50、33、25，计算50时又会用到25等）。我们可以用一个缓存存储已经计算过的结果，下次直接取：

#include<iostream>
#include<unordered_map>
using namespace std;

class a {
private:
    unordered_map<long long, long long> memo; // 用long long避免溢出，n可能很大

public:
    long long recur(long long n) {
        // 如果已经计算过，直接返回缓存值
        if (memo.find(n) != memo.end()) {
            return memo[n];
        }
        long long b = n / 2;
        if (b >= 1) { // 这里不用限制12，因为缓存会处理小数值
            b = recur(b);
        }
        long long c = n / 3;
        if (c >= 1) {
            c = recur(c);
        }
        long long d = n / 4;
        if (d >= 1) {
            d = recur(d);
        }
        long long res = max(b + c + d, n);
        memo[n] = res; // 存入缓存
        return res;
    }
};

int main() {
    a obj;
    long long n;
    while (cin >> n) {
        cout << obj.recur(n) << endl;
    }
    return 0;
}

补充说明 #

• 为什么用long long？因为当n很大时，拆分后的数值总和可能超过int的范围，会导致溢出错误。
• 为什么去掉>=12的判断？因为记忆化缓存会自动处理所有重复计算，即使是小数值，第一次计算后就会存入缓存，后续直接取用，效率更高。而且实际上当n<12时，直接返回n本身更划算（比如n=11拆分后是5+3+2=10，比原数小，所以应该返回11）。

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