动态规划解决剪绳子问题

有思路和解释

```
public int cuttingRope(int n){
    if (n<4) return n-1;//小于4的直接返回n-1
    int[] dp = new int[n+1];
    //初始化
    dp[1] = 0;
    dp[2] = 1;
    dp[3] = 2;
    //外层控制总的绳子长度
    for (int i = 4; i < dp.length; i++) {
        //为什么从2开始？
        //一段绳子，剪的话，剪成长度为1和剩下长度，相乘没有意义啊，所以从剪成2和剩余的开始
        //从2开始，然后可以剪成3和剩余、4和剩余、5和剩余。。。等
        //其中需要找出剪得最大值，即为当前绳子长度所能剪得的乘积最大值
        //内层控制当前绳子剪得位置
        for (int j = 2; j < i; j++) {
            //当前绳子可以剪成j长度和剩余的i-j长度，
            //1、Math.max(j*(i-j), j*dp[i-j])找出j长度和剩余长度的乘积最大值
            //j*(i-j)表示j长度乘以剩余长度，j*dp[i-j]表示j长度乘以剩余长度的可以继续剪切的乘积最大值
            //2、再一次和dp[i]，比较取最大值，因为当前绳子可以被剪成2长度和剩余长度，也可以被剪成3和剩余长度。。。
            //所以，需要在内循环中寻找当前绳子长度的乘积最大值
            'dp[i] = Math.max(dp[i], Math.max(j*(i-j), j*dp[i-j]));'
        }
    }
    return dp[n];
}
```