题解 | #矩阵中的路径#

数学方式解决 在做这题之前我们先来看这样一个问题: 一个整数先把他分成两部分，x+y=n（假设x>=y并且x-y<=1,也就是说x和y非常接近）那么乘积是xy。 然后我们再把这两部分的差放大(x+1)+(y-1)=n(假设x>=y)；他们的乘积是（x+1）(y-1)=xy-(x-y)-1，很明显是小于xy的，所以我们得出结论，如果把整数n分为两部分，那么这两部分的值相差越小乘积越大。

同理还可以证明如果分成3部分，4部分……也是相差越小乘积会越大。

根据上面的证明，如果我们把长度为n的绳子分为x段，则每段只有在长度相等的时候乘积最大，那么每段的长度是n/x。所以他们的乘积是(n/x)^x。我们来对这个函数求导

通过对函数求导我们发现，当x=n/e的时候，也就是每段绳子的长度是n/x=n/(n/e)=e的时候乘积最大。我们知道e=2.718281828459。而题中我们的绳子剪的长度都是整数，所以不可能取e，我们只能取接近e的值，也就是3的时候乘积最大。

但也有例外，当n<=4的时候会有特殊情况，因为22>13。明白了这点代码就容易多了，如果n大于4，我们不停的把绳子减去3，来看下代码

class Solution {
public:
    int cutRope(int number) {
        if(number == 2)
            return 1;
        if(number == 3)
            return 2;
        int res = 1;
        while(number > 4){
            res *= 3;
            number -= 3;
        }
        if(number == 4)
            return res * 4;
        else 
            return res * number;
    }
};

动态规划解决

定义一个数组dp，其中dp[i]表示的是长度为i的绳子能得到的最大乘积。我们先把长度为i的绳子拆成两部分，一部分是j，另一部分是i-j，那么会有下面4种情况

1. j和i-j都不能再拆了

   dp[i]=j*(i-j);

2. j能拆，i-j不能拆

   dp[i]=dp[j]*(i-j);

3. j不能拆，i-j能拆

   dp[i]=j*dp[i-j];

4. j和i-j都能拆

   dp[i]=dp[j]*dp[i-j];

我们取上面4种情况的最大值即可。我们把它整理一下，得到递推公式如下

dp[i] = max(dp[i], (max(j, dp[j])) * (max(i - j, dp[i - j])));

比如我们想计算长度为9的绳子，画个图来看一下:

    public int cutRope(int target) {
        int[] dp = new int[target + 1];
        dp[1] = 1;
        for (int i = 2; i <= target; i++) {
            for (int j = 1; j < i; j++) {
                dp[i] = Math.max(dp[i], (Math.max(j, dp[j])) * (Math.max(i - j, dp[i - j])));
            }
        }
        return dp[target];
    }

时间复杂度：O（n^2） 空间复杂度：O（n），需要数组dp的大小