动态规划从递归到结束

algorithm

---

分解整数

• 分解整数，题目大意，给定一个整数，分解成不少于两个整数的和，然后最大化这些和因子的乘积。例如：$2=1+1$ 乘积$f(2)=1*1, f(2)=1$，$10=3+3+4, f(10)= 3*3*4=36$
• 依据上面的题目解释可以知道题目的答题意思，假设dp(n) 表示n的分解乘积最大值。
• 直观想法，如果求$dp(n)$，那么可以转化为递归求解$dp(n-1)*1,dp(n-2)*2 \cdots dp(1)*(n-1)$的最大值，需要注意的地方是，$dp(2)$如果作为因子，也就是$dp(n)=dp(2)*(n-2)$，为了使乘积最大，$dp(2)$是需要等于2的，因为2可以选择不再分解，作为一个单独的因子。

方法一：递归

    int integerBreak(int n) {
        //base case :just return for base case 
        if(n <= 0)
            return 0;
        if(n == 2 || n == 1)
            return 1;
        if(n == 3)
            return 2;
        return intbreak(n);
    }
    int intbreak(int n) {
        if(n<=4)// case #1:the adder of sum
            return n;
        int r = 1;
        for(int i = 1; i < n-1; i++){
            int x = intbreak(n-i) * i;
            r = max(r,x);
        }
        return r;
    }

• 直接调用的是integerBreak,对于小于4的情况，可以作为基本情况返回。
• 下面的intbreak使用的是递归的调用，注意其递归的出口，小于4的情况，直接返回数。小于4的数作为因子，就是其本身。这里与integerBreak不同，integerBreak是分解后的结果。
• 时间复杂度:$T(n) = \sum^{n-1}_{1}{T(i)}=O(2^n)$
• 空间复杂度:$S(n) = \sum^{n-1}_{1}{S(i)}=O(n^2)$

方法二：转化为备忘录递归

• 上述方式存在子问题重复计算的情况，例如计算$dp(5)$,需要计算$dp(1) \cdots dp(4)$，计算$dp(4)$时，需要计算$dp(1) \cdots dp(3)$，我们用map，也可以用数组，来缓存已经计算完的数据。对于已经获取的数据直接返回结果。

    unordered_map<int,int> umap;
    int integerBreak(int n) {
        if(n <= 0)
            return 0;
        if(n == 2 || n == 1)
            return 1;
        if(n == 3)
            return 2;
        // base case for integer break as adder
        for(int i = 1; i<= 4;i++) {
            umap[i] = i;
        }
        return intbreak(n);
    }
    int intbreak(int n) {
        if(umap.find(n) != umap.end()) {
            return umap[n];
        }
        int r = 1;
        for(int i=1; i < n-1; i++){
            int x = intbreak(n-i) * i;
            r = max(r,x);
        }
        umap[n] = r;
        return r;
    }

• 时间复杂度：$O(n^2)$,空间复杂度：$O(n)$，需要使用哈希表

方法三：转化为递推（迭代）

• 基于上述的论述，能够看出，假设我们已经知道了$dp(1) \cdots dp(n-1)$ ，那么，我们遍历$1\cdots (n-1)$的情况下能否分解的乘积最大值，就可以找到$n$分解为多个数的乘积最大值，就是$dp(i) * (n-i),i \in [1,n-1]$的最大值。
• 注意的是，小于4的数，作为因子和最为分解的数的区别。

    int integerBreak(int n) {
        if(n <= 0)
            return 0;
        if(n == 2 || n == 1)
            return 1;
        if(n == 3)
            return 2;
        vector<int> dp(n+1,0);
        // base case for adder n < 4
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        int  x;
        for(int i = 4; i <= n; i++ ) {
            for(int k = i-1; k >= 1; k-- ) {
                x = dp[k] * (i-k);
                dp[i] = max(x,dp[i]);
            }
        }
        return dp[n];
    }

• 时间复杂度:$O(n^2)$,空间复杂度：$O(n)$

方法四：数学规律

• 假设数字为$n$，被分解为$\frac{n}{x}$个$x$相加，那么乘积$f(x) = x^{n/x}$，对函数求导:$f^{'}(x) = n*x^{n/x-2}*(1-ln(x))$,求得极值点为$x = e$

$$f^{'}(x) > 0, x < e \\ f^{'}(x) < 0, x > e \\ f^{'}(x) = 0, x = e \\ $$

• 所以，最大值出现的情况就是分解为2,3的因子，对$n>4$来说，$f(n) = 3^(n/3) * (n%3)$,对于$n<=4$的可认为是基本情况。

 public int integerBreak(int n) {
        if(n == 2) return 1;
        if(n == 3) return 2;
        int product = 1;
        while( n > 4){
            product *= 3;
            n -= 3;
        }
        product *= n;
        return product;
    }

• 最后一个方法参考leetcode讨论区，证明思路