面试题14：剪绳子

给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1，m<=n），每段绳子的长度记为k[1],...,k[m]。请问k[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

思路一：这个题目可以把大问题分解为若干个小问题或者说子问题，并将子问题的解存储起来，各种子问题的最优解组合起来就构成了大问题的最优解，所以此题可用动态规划来解决。时间复杂度为O(n^2)，空间复杂度为O(n)。

写成具体公式就是f(n)=max(f(i)*f(n-i))，其中0<i<n.
代码：

#include<iostream>
#include<vector>
#include<math.h>
#include<cstdio>
#include<string>
#include<stack>
using namespace std;

int cutRope(int number) {
    //异常情况处理
    if (number <= 1)
        return 0;
    //attention1:若输入很简单，直接返回结果
    if (number == 2)
        return 1;
    if (number == 3)
        return 2;

    //attention2:若输入很复杂，建立数组存储子问题的最优解
    int* product = new int[number + 1];
    memset(product, 0, number);
    product[1] = 1;
    product[2] = 2;
    product[3] = 3;

    //从4开始循环，一直到number，存储子问题最优解，最后解出product(number)
    for (int n = 4; n <= number; n++)
    {
        int max = 0;
        for (int m = 1; m <= n / 2; m++)
        {
            product[n] = product[m] * product[n - m];
            if (max < product[n])
                max = product[n];
        }
        product[n] = max;
        cout << n << "  " << product[n] << endl;

    }

    int result = product[number];
    delete[] product;
    return result;
}

int main()
{
    int number = 15;
    cout << cutRope(number) << endl;
    return 0;
}

Q:什么样的题适合用动态规划？

A：一般，动态规划有以下几种分类：

最值型动态规划，比如求最大，最小值是多少
计数型动态规划，比如换硬币，有多少种换法
坐标型动态规划，比如在m*n矩阵求最值型，计数型，一般是二维矩阵
区间型动态规划，比如在区间中求最值
其实，根据此题的启发，我们可以换种想法，就是什么样的题适合用暴力递归？
显然就是，可能的情况很多，需要枚举所有种情况。只不过动态规划，只记录子结构中最优的解。
特别注意attention1与attention2的区别：attention1中是当n=0,1,2,3直接返回这些简单的值所对应的最优解；但attention2所对应的n的值就是较为复杂的数了，n>=4，这里面的1,2,3就是i的值，有自己的含义，当i=1时，表示有一段长度为切为1，剩下n-1，与题目中m！=1不对立，所以product[]中存储的值是只针对n>=4而言的。

思路2：暴力递归解法

/*
暴力递归就要想到递归三部曲：
1. 递归函数的设计和功能：back_track(n); 含义是：求长度为n的数，最后分段后的最大乘积，这里我们不需要关心分成多少段
2. 递归函数的终止条件: 如果n <= 4, 显然back_track(n) = n，初始条件也就是我们不用计算就能得到的。
3. 下一步递归：对于长度n，我们需要减少递归参数n，如果第一段为1， 显然下一步递归为back_track(n-1),如果第一段为2， 则下一步递归为back_track(n-2)...因为要至少分2段，
所以，最后一次可能的情况为最后一段为n-1, 下一步递归为back_track(1)，因此，每一步可能的结果为1 * back_track(n-1), 2*back_track(n-2), ..., (n-1) * back_track(1),
在n-1种情况中取一个最大值即可。 这里我们不用关系back_track(n-1)等的值为多少，因为最终会递归到我们的终止条件，因此绝对是可以求出来。
*/
int back_track(int n)
{
    if (n <= 4)
        return n;
    int maxProduct = 0;
    for (int i = 1; i < n; ++i)
    {
        maxProduct = max(maxProduct, back_track(i) * back_track(n - i));
    }
    return maxProduct;
}
int cutRope(int number)
{
    if (number <= 0)
        return 0;
    if (number == 1)
        return 1;
    if (number == 2)
        return 1;
    if (number == 3)
        return 2;
    return back_track(number);
}