《Powers of Two》题目分析

首先在表示n的时候，对于一个确定的k，使用2个(+2^k)或者2个(-2^k)或者一个(+2^k)和一个(-2^k)都是不合理的。所以最多只可能用1个(+2^k)或者1个(-2^k)。

如果n是偶数，表示n的时候显然不应该用2^0。因为如果用就至少用2个，不合理。

如果n是奇数，表示n的时候可能用1个+2^0或者1个-2^0。

所以我们可以用递归+记忆化搜索来求解答案。

map<int, int> f;
int calc(int n) {
    if (f.find(n) == f.end()) {
        int s;
        if (n % 2 == 0) s = calc(n / 2);
        else if (n == 1) s = 1;
        else s = min(calc(n - 1), calc(n + 1)) + 1;
        f[n] = s;
    }
    return f[n];
}