leetcode 343. Integer Break 深度优先遍历DFS(超时) + 最大子元素乘积 + 发现规律

系统管理员 2022-06-07 01:15 132阅读 0赞

Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).

Note: You may assume that n is not less than 2 and not larger than 58.

Credits:  
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

题意很简单，直接DFS深度优先遍历肯定会超时，网上看了个做法，结果说明分割成3的乘积最大，具体为什么呢，我就不管了。

**这道题的难点其实在于证明为什么拆出足够多的 3 就能使得乘积最。**

代码如下：

import java.util.ArrayList;
    import java.util.List;
    
    /*
     * 这道题的难点其实在于证明为什么拆出足够多的 3 就能使得乘积最。 
     * http://blog.csdn.net/liyuanbhu/article/details/51198124
     * */
    class Solution 
    {
        public int integerBreak(int n) 
        {
            if(n ==1)
                return 0;
            else if(n==2)
                return 1;
            else if(n==3)
                return 2;
            else if(n==4)
                return 4;
    
            int res = 1;
            while(n>=3)//看n包含多少个3,把他们相乘,直到n<=2
            {
                res *= 3;
                n -= 3;
            }
    
            if(n == 0) 
                return res;//n可以整除3，res就是各个3相乘
            else if(n == 1)
                return (res / 3 ) * 4;//除3余1，把其中的一个3加1变为4再相乘
            else if(n == 2) 
                return res * 2;//除3余2,则可直接把2与res相乘
            return res;
        }
    
    
        int max=-1;
        public int integerBreakByDFS(int n) 
        {
            List<Integer> one=new ArrayList<Integer>();
            breakAll(n,one);
            return max;
        }
    
        public void breakAll(int n, List<Integer> one) 
        {
            if(n==0)
            {
                int pro=1;
                for(int i=0;i<one.size();i++)
                    pro*=one.get(i);
                max=Math.max(max, pro);
                return ;
            }else 
            {
                if(one.size()==0)
                {
                    for(int i=1;i<n;i++)
                    {
                        one.add(i);
                        breakAll(n-i,one);
                        one.remove(one.size()-1);
                    }
                }else
                {
                    for(int i=1;i<=n;i++)
                    {
                        one.add(i);
                        breakAll(n-i,one);
                        one.remove(one.size()-1);
                    }
                }
            }   
        }
    }

下面是C++的做法

**这道题的解决思路就是寻找有多少个3**

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    class Solution 
    {
    public:
    
        int integerBreak(int n)
        {
            if (n == 1)
                return 0;
            else if (n == 2)
                return 1;
            else if (n == 3)
                return 2;
            else if (n == 4)
                return 4;
    
            int res = 1;
            while (n >= 3)
            {
                n -= 3;
                res *= 3;
            }
    
            if (n == 0)
                return res;
            else if (n == 1)
                return (res / 3) * 4;
            else if (n == 2)
                return res * 2;
    
        }
    
    
        int res = 0;
        int integerBreakByDFS(int n) 
        {
            dfs(n, vector<int>());
            return res;
        }
    
        void dfs(int n, vector<int> one)
        {
            if (n == 0)
            {
                int a = 1;
                for (int i : one)
                    a *= i;
                res = max(res, a);
            }
            else
            {
                if (one.size() == 0)
                {
                    for (int i = 1; i < n; i++)
                    {
                        one.push_back(i);
                        dfs(n - i, one);
                        one.pop_back();
                    }
                }
                else
                {
                    for (int i = 1; i <= n; i++)
                    {
                        one.push_back(i);
                        dfs(n - i, one);
                        one.pop_back();
                    }
                }
            }
        }
    
    };