题解 | 剪绳子

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int cutRope(int n) {
        // write code here
        int f[80]={0};
        f[1] = 1, f[2] = 2, f[3] = 3;
        if(n<=3) return n;
        for(int i = 4; i <= n; ++i){
            for(int j = 2; j <= (i/2)+1; ++j){
                if(f[i]<f[j]*f[i-j]){
                    f[i] = f[j]*f[i-j];
                }
            }
        }
        return f[n];
    }
};

对这种数学性一看就很强的题目，最好是建立数学模型，但是我今天不是很想算，所以准备看看动态规划能不能解决这个问题。

首先考虑怎么分配子问题，如果要拆成每一个加法组合那么肯定不能做，运算量太大了。

于是我考虑能不能使用贪婪算法，就要两个东西相乘看是否符合局部最优。

然后我列了ab-a-b的式子，运用还没有忘干净的因式分解分成了(a-1)(b-1)-1，我发现当a和b都是整数，当它们都大于1的时候就能得到非负数了，也就是说一个数能拆成大家都在1以上的数就要拆。

这个发现很有启迪性，我又发现不能统统拆成1以上的数字（就是2+2=4）是1、2、3。

结合这两条结论，我得到大家都会拆成2和3的模样，而2和3合在一起没有更好的拆法了（有的人可能考虑2、2、2变3、3，我这里直接告诉你不会，因为在两两拼的时候就会有3、3）。

所以我得到最终结论，我可以使用贪婪算法，局部的最优能够成为全局的最优，而且只需要拆成两个就行。

因为大的由小的构成，所以从小到大（毕竟是动态规划，从小到大？），依次考虑从2开始拆能怎么两两拆分。

因为过了一半就是两个相加的数反过来了，没什么意义，所以我让它找到中点就结束（找远的那个是因为在其他更一般的题中为了搞全我习惯这样处理，其实直接除以2也行，当然这是1开始的情况，0开始就不一样了）。

首先全置为0，然后初始化1、2、3，最后开始遍历换后面的部分，最后其实每个都得到了最好的结果（最大乘积），我们输出最后一个作为这个参数的结果。