leetcode 808. Soup Servings 分汤

Problem: 808. Soup Servings 分汤

解题过程

深度优先搜索，记忆化搜索，而且当n足够大的时候，四种情况出现的概率相等，那么2和4合并起来就是100+100，3是50+50，1是100+0，2和4、3情况都是相等的，1是A倒完，所以当n足够大的时候，肯定是A先倒完，概率是100% = 1.0

记忆化搜索的key使用了数值右移，使用了数据类型unsigned long long

Code

class Solution { public: unsigned long long sumA = 0, sumEqual = 0; double sum = 0.0; unordered_map<unsigned long long, double> ump; double dfs(int na, int nb, int steps) { if(na > 0 && nb <= 0) return 0.0; if(na <= 0) { if(nb > 0) { return 1.0; } else if(nb <= 0) { return 0.5; } } unsigned long long key = ((unsigned long long)na << 40) + ((unsigned long long)nb<<20) + (unsigned long long)steps; if(ump.find(key)!=ump.end()) return ump[key]; double ret = 0.0; ret += dfs(na - 100, nb, steps + 1) * 0.25; ret += dfs(na - 75, nb-25, steps + 1) * 0.25; ret += dfs(na - 50, nb-50, steps + 1) * 0.25; ret += dfs(na - 25, nb-75, steps + 1) * 0.25; ump[key] = ret; return ret; } double soupServings(int n) { if(n >= 4900) return 1.0; double ans = dfs(n, n, 0); return ans; } };