深搜

class Solution {
public:
    unordered_map<int, int> dp;
    int dfs(int n){
        if (n == 1) return 1;
        if (n == 2) return 2;
        if (dp.count(n)) {
            return dp[n];
        }

        // 如果n不是2的倍数， 就花费1天，吃掉一个。 使剩余的变为2的倍数。
        // 如果n不是3的倍数， 就花费1天或2天，每天吃掉一个，使剩余变为3的倍数。
        int t1 = 1 + dfs(n/2) + n%2;
        int t2 = 1 + dfs(n/3) + n%3;
        int ans = min(t1, t2);
        //cout << n << " " << ans << endl;
        dp[n] = ans;
        return ans;
    }
    int minDays(int n) {
        int ans = 0;
        ans = dfs(n);
        return ans;
    }
};