DP: Top-down is faster than bottom-up

Problem

1553. Minimum Number of Days to Eat N Oranges

Bottom-up got TLE

In order to speed it up, use the 2*i-1, 3*i-1, or 3*i-2 to replace the subtract by one.

class Solution {
public:
    int minDays(int n) {
        if (n==1)return 1;
        vector<int> dp(n+1, INT_MAX);
        dp[1] = 1;
        for (int i = 1; i <= n; ++i)
        {
            if (2*i<=n)
                dp[2*i] = min(dp[i]+1, dp[2*i]);
            else break;
            if (2*i+1<=n)dp[2*i+1] = min(dp[i]+2, dp[2*i+1]);
            if (3*i<=n)dp[3*i] = min(dp[i] + 1, dp[3*i]);
            else continue;
            if (3*i+1<=n)dp[3*i+1] = min(dp[i] + 2, dp[3*i+1]);
            if (3*i+2<=n)dp[3*i+2] = min(dp[i] + 3, dp[3*i+2]);
        }
        return dp[n];
}
};

Top-Down got AC

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

Thanks for reading.