1553. Minimum Number of Days to Eat N Oranges

起初用dp, 速度竟然太慢, 時間複雜度為Ｏ(n)

class Solution {
public:
    int minDays(int n) {
        vector<int> dp(n + 1, n);
        if(n == 1 ) return 1;
        if(n == 2 || n == 3) return 2;
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 2;
        for(int i = 4; i <= n; i++){
            if( i % 2 == 0 && i % 3 == 0){
                dp[i] = min({dp[i - 2 * (i / 3)] + 1, dp[i], dp[i / 2] + 1});
                continue;
            }
            if(i % 2 == 0){
                dp[i] = min(dp[i / 2] + 1, dp[i]);
            }else if(i % 3 == 0){
                dp[i] = min(dp[i - 2 * (i / 3)] + 1, dp[i]);
            }
            dp[i] = min(dp[i - 1] + 1, dp[i]);
        }
        return dp[n];
    }
};

要回歸到最初的dfs, 可以在logn的時間內完成

T(n) = 2T(n / 2) + O(1)

記得用一個hashtable去紀錄, 可以避免掉重複的運算

class Solution {
public:
    
    unordered_map<int, int> m;
    int minDays(int n) {
        if(n < 2) return 1;
        if(!m.count(n)){
            m[n] = 1 + min(n % 2 + minDays(n/ 2), n % 3 + minDays(n / 3));
        }
        return m[n];
    }
};