力扣1553 2024.5.13

原题网址：此处为链接

个人难度评价：1700

分析：
虽然不知道为什么贪心不对，但总之贪心不对。数据如此大也难以DP，那么只有搜索了。显然有一眼可得的搜索记忆化：记忆当只剩下k个果时还需要几天。
值得一提的是，本代码实际上可能并不是一个正解代码，其可能无法在整数域上保证所有答案正确，但在1e9范围内已经可以得到正确答案。
原因为本代码迭代时，针对选择三：吃一个果并没有做出特殊优化。但即使在一定步数后你会把大部分情况都记忆下来使每一次-1的复杂度降低，你也无法让操作过大（起码不能超过1e4）。但把操作限制在1e3内确实可以得到正确答案。理想情况下最多其实30步左右就应该可以把果吃完（每次吃一半甚至吃三分之二），但操作限制在100无法通过。

源码：

// 1553
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;

class Solution {
public:
    unordered_map<int, int> p;
    int dfs(int h, int now){
        if (now == 0){
            return h;
        }
        if (p.find(now) != p.end())
            return p[now]+h;
        if (h >= 1000)
            return INF;
        int res = INF;
        if (now % 2 == 0){
            res = min(res, dfs(h+1, now/2));
        }
        if (now % 3 == 0){
            res = min(res, dfs(h+1, now/3));
        }
        res = min(res, dfs(h+1, now-1));
        p[now] = res-h;
        return res;
    }

    int minDays(int n) {
        int ans = dfs(0, n);
        return ans;
    }
};