《剑指offer》c++版本 14.剪绳子

本题在牛客网剑指offer专项里没看到，原书第二版上有，如题：

这道题是开放的动态规划题，题目中只给了绳子长度，却没定义具体剪多少段，初遇此题，难以下手，看了题解，豁然开朗。设f(n)为常为n的绳子剪成m段之后可得最大值，则存在n-1中减法，得f(n) = MAX(f(i) * f(n-i))；初始值f(1),f(2),f(3)都可以计算出来，大于3则调用dp方程递归计算至n即可。

思路简单，两次遇到都没能够想到。(+_+)?，接着练习。

下面是本题的c++解法：

inline int getMax(int a, int b)
{
    return ((a) > (b) ? (a) : (b));
}

class Solution {
public:
    int maxDivision(int n)
    {
        int max = 0;
        vector<int> dp(n+1,0);

        //特殊处理
        if (n < 2)
            return 0;
        if (n == 2)
            return 1;
        if (n == 3)
            return 2;

        //边界初始化
        for (int i = 0; i < 4; i++)
            dp[i] = i;

        //状态递推
        for (int i = 4; i <= n; i++)
        {
            for (int j = 1; j <= i/2; j++)
            {
                max = dp[j] * dp[i - j];
                dp[i] = getMax(dp[i], max);
            }
        }

        return dp[n];
    }
};

=============================================================================================

Linux应用程序、内核、驱动、后台开发交流讨论群(745510310)，感兴趣的同学可以加群讨论、交流、资料查找等，前进的道路上，你不是一个人奥^_^。