寫在前面

這期的周賽題，本來抱著試試看的想法報名的，參加了之后發(fā)現(xiàn)還是比較簡單的，雖然這道題最后也沒拿到分，不過學(xué)到了DP的細節(jié)處理，感覺還是很劃算的。

題目

思路分析

這道題給的題目解釋實在是太明顯了，要求f(n)，可以根據(jù)f(n - 1)，f(n / 2) ，f(n / 3)取最小值作為結(jié)果，顯然要么遞歸求解，要么動態(tài)規(guī)劃，我當(dāng)時還在想，最后的hard問題這么簡單的嗎？結(jié)果寫出來提交發(fā)現(xiàn)內(nèi)存超了，題目中給定的n的范圍最大到20e，如果存儲所有的結(jié)果肯定會超出內(nèi)存限制了。。。所以無論是使用動態(tài)規(guī)劃還是使用備忘錄遞歸，得到的結(jié)果都將是超出內(nèi)存限制，那么思路就變成了怎么存儲盡量少的結(jié)果得到答案。
首先我們考慮對于任意的n有什么情況計算天數(shù)。

• n 不是2也不是3的倍數(shù)：n = n - 1;
• n 是2的倍數(shù)：n = n / 2;
• n 是3的倍數(shù)：n = n / 3;
  不過這只是題目給出的三種選擇，實際上，對于第一種選擇，他的可能性只有幾種，而且直觀來講，n /= 2 或者 n /= 3 肯定比 n -= 1變化的快，故盡可能湊出n /= 2 或者 n /= 3，對最終的結(jié)果是有益處的，那么可以得到如下的選擇。
• n % 2 = 1：n = (n - 1) / 2; 這個過程需要兩天
• n % 3 = 1：n = (n - 1) / 3; 這個過程需要兩天
• n % 3 = 2：n = (n - 1 -1) / 3; 這個過程需要三天
• n % 2 = 0：n = n / 2; 這個過程需要一天
• n % 3 = 0：n = n / 3; 這個過程需要一天
  總結(jié)出來大概是這么五種情況，其實直接按照這五種情況來記憶化遞歸就可以得到最終的結(jié)果了，并且時間空間都滿足條件?？梢詤⒖枷逻叺拇a。

完整代碼

基礎(chǔ)代碼

class Solution {
    private Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    public int minDays(int n) {
        if(n == 1){
            return 1;
        }

        if(map.containsKey(n)){
            return map.get(n);
        }

        int temp = Integer.MAX_VALUE;

        if(n % 2 == 0){
            temp = Math.min(minDays(n / 2) + 1, temp);
        }
        if(n % 2 != 0 && n > 1){
            temp = Math.min(minDays((n - 1) / 2) + 2, temp);
        }
        if(n % 3 == 0){
            temp = Math.min(minDays(n / 3) + 1, temp);
        }
        if((n - 1) % 3 == 0 && n > 1){
            temp = Math.min(minDays((n - 1) / 3) + 2, temp);
        }
        if((n - 2) % 3 == 0 && n > 2){
            temp = Math.min(minDays((n - 2) / 3) + 3, temp);
        }
        map.put(n, temp);
        return temp;
    }
}

通過上邊五種情況的劃分，使得在存儲已經(jīng)計算的結(jié)果時，減少了n - 1部分值的計算，另外由于自頂向下遞歸求解，實際存儲的數(shù)據(jù)量大概在O(logn)級別，時間復(fù)雜度也是同樣，大大節(jié)約了空間與時間，當(dāng)然這里的數(shù)據(jù)量可能不容易看出，可以通過后邊深入了解。
這樣寫出的代碼提交之后已經(jīng)可以獲得雙百(8月16日，4ms，38.5mb內(nèi)存)，不過去看那些得了周賽前幾名的代碼會發(fā)現(xiàn)他們的代碼很簡潔，遞歸只有幾行，相比之下這份代碼就冗余了很多，所以拆分了選擇之后還需要進行整合。
我們通過上邊的五種情況的計算方法再來分析：

• minDays(n / 2) + 1
• minDays((n - 1) / 2) + 2
• minDays(n / 3) + 1
• minDays((n - 1) / 3) + 2
• minDays((n - 2) / 3) + 3
  他們又可以劃分為 除以2 的選擇與 除以3 的選擇，而對這兩類選擇，計算是類似的，所以我們考慮 除以3 的選擇。由于對于每一個n，都要計算每種選擇，所以不妨單抽出一個任意數(shù)n進行分析。
• minDays(n / 3) + 1
• minDays((n - 1) / 3) + 2
• minDays((n - 2) / 3) + 3
  我們假設(shè) n % 3 == 2; 其他的余數(shù)情況也是類似的。在此情況下，n / 3; (n - 1) / 3; (n - 2) / 3;三者對應(yīng)的數(shù)是相等的(Java下取整)，均為(n - 2) / 3，所以三種選擇可以寫為如下方式：
• minDays((n - 2) / 3) + 1 + 0
• minDays((n - 2) / 3) + 1 + 1
• minDays((n - 2) / 3) + 1 + 2
  這里拆出一個1是對應(yīng)選擇 除以三 的那一天，可以發(fā)現(xiàn)剩余的加數(shù)恰好與 n % 3相等，所以這三種選擇就可以整合為：minDays(n / 3) + 1 + n % 3，這也就是好多大神的寫法了，十分的精煉，同理 除以二 的部分可以寫成 minDays(n / 2) + 1 + n % 2。這樣代碼一下就簡單了許多，而且也更容易發(fā)現(xiàn)空間的使用量，對于每個 n ，只存儲了 n / 2 與 n / 3 的結(jié)果，也就是n是指數(shù)級減小的，速度更快而且使用的空間也更小。

改進后的代碼

class Solution {
    private Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    public int minDays(int n) {
        if(n == 0)
            return 0;
        if(!map.containsKey(n)){
            int temp = n;
            int half = n / 2;
            int third = n / 3;
            temp = Math.min(minDays(half) + n % 2 + 1, temp);
            temp = Math.min(minDays(third) + n % 3 + 1, temp);
            map.put(n, temp);
        }
        return map.get(n);
    }
}

代碼簡潔而且高效，思路真的是很巧妙。
文章有寫的不對的地方還請指出。感恩相遇~