写在前面

这期的周赛题，本来抱着试试看的想法报名的，参加了之后发现还是比较简单的，虽然这道题最后也没拿到分，不过学到了DP的细节处理，感觉还是很划算的。

题目

思路分析

这道题给的题目解释实在是太明显了，要求f(n)，可以根据f(n - 1)，f(n / 2) ，f(n / 3)取最小值作为结果，显然要么递归求解，要么动态规划，我当时还在想，最后的hard问题这么简单的吗？结果写出来提交发现内存超了，题目中给定的n的范围最大到20e，如果存储所有的结果肯定会超出内存限制了。。。所以无论是使用动态规划还是使用备忘录递归，得到的结果都将是超出内存限制，那么思路就变成了怎么存储尽量少的结果得到答案。
首先我们考虑对于任意的n有什么情况计算天数。

• n 不是2也不是3的倍数：n = n - 1;
• n 是2的倍数：n = n / 2;
• n 是3的倍数：n = n / 3;
  不过这只是题目给出的三种选择，实际上，对于第一种选择，他的可能性只有几种，而且直观来讲，n /= 2 或者 n /= 3 肯定比 n -= 1变化的快，故尽可能凑出n /= 2 或者 n /= 3，对最终的结果是有益处的，那么可以得到如下的选择。
• 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; 这个过程需要一天
  总结出来大概是这么五种情况，其实直接按照这五种情况来记忆化递归就可以得到最终的结果了，并且时间空间都满足条件。可以参考下边的代码。

完整代码

基础代码

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;
    }
}

通过上边五种情况的划分，使得在存储已经计算的结果时，减少了n - 1部分值的计算，另外由于自顶向下递归求解，实际存储的数据量大概在O(logn)级别，时间复杂度也是同样，大大节约了空间与时间，当然这里的数据量可能不容易看出，可以通过后边深入了解。
这样写出的代码提交之后已经可以获得双百(8月16日，4ms，38.5mb内存)，不过去看那些得了周赛前几名的代码会发现他们的代码很简洁，递归只有几行，相比之下这份代码就冗余了很多，所以拆分了选择之后还需要进行整合。
我们通过上边的五种情况的计算方法再来分析：

• 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，都要计算每种选择，所以不妨单抽出一个任意数n进行分析。
• minDays(n / 3) + 1
• minDays((n - 1) / 3) + 2
• minDays((n - 2) / 3) + 3
  我们假设 n % 3 == 2; 其他的余数情况也是类似的。在此情况下，n / 3; (n - 1) / 3; (n - 2) / 3;三者对应的数是相等的(Java下取整)，均为(n - 2) / 3，所以三种选择可以写为如下方式：
• minDays((n - 2) / 3) + 1 + 0
• minDays((n - 2) / 3) + 1 + 1
• minDays((n - 2) / 3) + 1 + 2
  这里拆出一个1是对应选择 除以三 的那一天，可以发现剩余的加数恰好与 n % 3相等，所以这三种选择就可以整合为：minDays(n / 3) + 1 + n % 3，这也就是好多大神的写法了，十分的精炼，同理 除以二 的部分可以写成 minDays(n / 2) + 1 + n % 2。这样代码一下就简单了许多，而且也更容易发现空间的使用量，对于每个 n ，只存储了 n / 2 与 n / 3 的结果，也就是n是指数级减小的，速度更快而且使用的空间也更小。

改进后的代码

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);
    }
}

代码简洁而且高效，思路真的是很巧妙。
文章有写的不对的地方还请指出。感恩相遇~