Function题解集合
- 记忆化搜索
记忆化搜索
还是把本题转化为对一棵多叉树的遍历，但是题目中也暗示我们会存在很多重复计算，那么现在关键就在于找到这些重复计算，并且想办法免去这些重复计算，下面看图:
这里假设a=b=c=3
上图中相同形状用green圈出来的部分代表着是重复计算过程，可以通过哈希容器记录保存，避免重复计算
代码:
代码语言：javascript复制#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<numeric>
#include<string>
#include<map>
class Solution {
map<vector<long>, long> cache;
public:
int w(long a,long b,long c)
{
if (cache.find({ a,b,c }) != cache.end()) return cache[{a, b, c}];
if (a <= 0 || b <= 0 || c <= 0) return 1;
if (a > 20 || b > 20 || c > 20) return w(20, 20, 20);
if (a < b && b < c) return cache[{a, b, c}]=w(a,b,c-1) w(a,b-1,c-1)-w(a,b-1,c);
return cache[{a, b, c}] = w(a-1, b, c) w(a-1,b-1, c) w(a-1, b,c-1)-w(a-1,b-1, c-1);
}
};
int main()
{
Solution s;
int a(0), b(0), c(0);
vector<vector<long>> ret;
while (1)
{
cin >> a >> b >> c;
if (a ==-1&&b==-1&&c==-1) break;
vector<long> num = { a,b,c };
ret.emplace_back(num);
}
for (int i = 0; i < ret.size(); i )
{
cout << "w(" << ret[i][0] << ", " << ret[i][1] << ", " << ret[i][2] << ")" << " = " << s.w(ret[i][0], ret[i][1], ret[i][2])<<endl;
}
return 0;
}
