笔者现在还未到找实习工作的时候。但正好是实习生招聘季，有幸有一些参加实习生招聘的朋友找我讨论一些大公司的笔试题目。笔者觉得今年的腾讯的测试题目小Q硬币问题（2017年腾讯笔试题）出的还是比较有意思的，角度也很刁钻。网易也出了同样角度的题目，便拿来和大家分享一下。
题目的大致描述：
小Q非常富有，拥有非常多的硬币，小Q的拥有的硬币是有规律的，对于所有的非负整数k,小Q恰好各有两个数值为2^k的硬币，所以小Q拥有的硬币是1，1，2，2，4，4……，小Q卖东西需要支付元钱，请问小Q想知道有多少种组合方案。
输入：一个n (1 <= n <= 10^18)，代表要付的钱 。
输出：表示小Q可以拼凑的方案数目。
输入样例：
6
输出样例：
3
即：4+2，4+1+1，2+2+1+1。
这个题目实际上是17年的招聘笔试题目了，只是今年重新拿过来当作测试题目使用了。光笔者能够通过搜索引擎搜索到的解法就有4种之多，然而没有一种是正解。对于一道算法题目，这里的正解当然是指在规定的时间和规定的空间下解决问题了。这4种解法大家可以通过腾讯笔试题：小Q硬币组合的博文了解到，笔者就不一一重述了。
关于题目的限制，由于笔者也未参加过17年的笔试，不知道当时的题干描述具体是什么。但是在今年的题目描述种明确限制了2s（对于C/C++）的时间限制，这无疑是这道题目的核心难点。实际上这也是出题人故意设置的一个坑吧233（不太能百度到解法）。
朴素搜索解法：
也可以叫做是递归的解法吧（笔者对算法的称呼没有太多了解XD）。对于其他的解法大家参考上面链接中的文章就可以了，但是复杂度都非常非常高，最快也要O(N)，对于这个10^18的N我们是不能接受的。从算法竞赛的角度，这个N的范围明摆着你要给出一个O(logN)的复杂度的算法才行呀。
先考虑最简单的搜索解法。通过推导（笔者这里就不具体推导了，请读者自行推导）我们可以把问题分为两种情况，假设F(N)表示对于数字N所能组合的方案数：
- N为奇数：F(N) = F(N / 2)。
- N为偶数：F(N) = F(N / 2 - 1) + F(N / 2)。
- 边界：F(0) = F(1) = 1。
这种搜索的思路和我们本科学习算法设计课中的整数划分的思维很像。而且编码非常容易，会写递归就能写出正确的程序来。
显然这种做法不仅时间复杂度过高，空间复杂度也很高。粗略的计算可以发现，最多的深度为logN层，这里这棵搜索树的大小还是太大了。所以我们需要剪枝，也就是所谓的记忆化搜索。
记忆化搜索解法：
所谓记忆化搜索，实际上和动态规划（以下简称DP）是同样的思维模式，减少重复的没有必要的计算，保存当前状态的最优解。大部分的DP算法的程序都可以和记忆化搜索相互转化。对于我们上面提出的方案，可以发现有很多很多重复的计算。如果我们把每个N的方案数都保存下来，如果计算过了我们直接返回值，就不要再递归去做了。同样容易证明如果我们记录的当前状态的方案数，我们的搜索树将被减少到每层2～3个结点，和具体输入的N有关，但是搜索的结点数量级在O(C*logN)，其中C<3。
那么问题来了：
- 第一：如何实现它。
- 第二：为什么要这么做，这么做的区别和普通DP算法有什么样的区别。
首先回答第一个问题，其实很简单，很多读者可能想到使用一个二维数组来对应表示不同的状态下的方案数，显然这个N的范围限制了我们这么做。反过来想想，我们使用二维数组来做记忆的初衷是什么？是O(1)的查询复杂度，典型的空间换时间。我们现在的状态树不会超过O(3*logN)，对于10^18的N来说，这个数字也不会超过200，那么我们直接使用线性表（or链表）来存放这200个数字不久可以了么？同样的这里还可以优化查询，因为我们的搜索是有序的，可以二分查找来优化。综上所述，这里给出一个笔者未优化查询的版本：
#include <iostream>
#include <vector>
using namespace std;
typedef unsigned long long ULL;
typedef std::pair<ULL, ULL> Pair; // 用一个数对来记录状态
vector<Pair> vis; // 用vector来模拟线性数据结构
ULL check(ULL n) { // 没有优化的粗暴查询
for (auto i : vis) {
if (i.first == n)
return i.second;
}
return -1;
}
ULL solve(ULL n) { // 淳朴的递归，但并不盲目
if (check(n) != -1)
return check(n);
else if (n & 1) {
ULL ans = solve(n >> 1);
vis.push_back(Pair(n, ans));
return ans;
} else {
ULL ans = solve((n >> 1) - 1) + solve(n >> 1);
vis.push_back(Pair(n, ans));
return ans;
}
}
int main() {
ULL in;
cin >> in;
vis.push_back(Pair(0, 1));
vis.push_back(Pair(1, 1));
ULL ans = solve(in);
cout << ans << endl;
return 0;
}
经笔者测试，上述代码对于N = 10^18来说是毫秒级别的。
那么，第二个问题。为什么普通的DP算法在这里失效了？笔者理解的是因为我们在做递推的时候，一定会从1 -> N，对于这道题目，从搜索树的大小变相的可以发现，我们在平常使用的DP算法中的状态数组，有很多很多数字是没有背用到的，因为我们每次递归下去的操作，都是在除以2，也就是在做O(LogN)级别的操作。但是同时，我们又很难确定出来，我们如何从初始状态，来推出我们这些新的状态（和搜索想法，搜索是递归的过程，从最后状态出发）。所以结论是，在搜索树深度不大，无法确定递推顺序的时候，记忆化搜索才是更好的选择。
小结
其实已经在上一个部分总结过了，这是笔者在简书的第一篇文章。想说的是笔者一般对于目前百度不到结果的有趣的内容才会写一些随笔和感想。
两个方面：
- 一方面是笔者的解法和结论不一定就是完全正确的，毕竟搜索引擎的结果表示也没有人公开过这些问题的标准答案，都是笔者自己完成的。若是哪里有问题，非常欢迎大家在下方评论指出，我们共同学习共同进步。
- 另一方面说给那些不尊重别人劳动成果的人，转载麻烦注明出处，谢谢。
祝各位正在找实习的在校生们一切顺利哟～
网友评论