剑指 Offer 14- I. 剪绳子

方法一：数学推导/贪心思想

解题思路：

数学推导：1.当所有绳段长度相等时，乘积最大。2.最优绳长度为3

切分规则：

1. 最优： 3，把绳子尽可能切分为长度为3的片段
2. 次优： 2，若最后一段为2，则保留
3. 最差： 1，若最后一段为1，则把3+1替换为2+2，因为 2 × 2 > 3 × 1 2times2 > 3times1 2×2>3×1

算法流程：

1. 当 n < = 3 n<=3 n<=3时，返回 n − 1 n-1 n−1
2. 当 n > 3 n>3 n>3时，求 a = n / 3 a=n/3 a=n/3和 b = n b=n b=n% 3 3 3，若
   • b = 0 b=0 b=0，直接返回 3 a 3^a 3a
   • b = 1 b=1 b=1，返回 3 a − 1 × 4 3^{a-1}times4 3a−1×4
   • b = 2 b=2 b=2，返回 3 a × 2 3^atimes2 3a×2

class Solution {
    public int cuttingRope(int n) {
        if (n <= 3) {
            return n - 1;
        }
        int a = n / 3;
        if (n % 3 == 0) {
            return (int)Math.pow(3, a);
        } else if (n % 3 == 1) {
            return (int)Math.pow(3, a - 1) * 4;
        } else {
            return (int)Math.pow(3, a) * 2;
        }
    }
}

方法二：动态规划

解题思路：

1. 设置数组dp记录0~n剪绳子的最大乘积。
2. 两层遍历：第一层i表示绳子的长度，第二层j表示第一段减去的长度。
   • 剪绳子： m a x ( j ∗ d p [ i − j ] , j ∗ ( i − j ) ) max(j*dp[i-j], j*(i-j)) max(j∗dp[i−j],j∗(i−j))
   • 减第一段，第二段不减： j ∗ ( i − j ) j*(i-j) j∗(i−j)
   • 不剪： d p [ i ] dp[i] dp[i]

j的优化，假设：

1. i = 7 , j = 2 。 d p [ 7 ] = m a x ( d p [ 7 ] , 2 ∗ 5 , 2 ∗ d p [ 5 ] ) i = 7 , j = 2。dp[7] = max( dp[7] , 2 * 5, 2 * dp[5]) i=7,j=2。dp[7]=max(dp[7],2∗5,2∗dp[5])

2. i = 7 , j = 5 。 d p [ 7 ] = m a x ( d p [ 7 ] , 5 ∗ 2 , 5 ∗ d p [ 2 ] ) i = 7 , j = 5。dp[7] = max( dp[7] , 5 * 2, 5 * dp[2]) i=7,j=5。dp[7]=max(dp[7],5∗2,5∗dp[2])，

   又因为： d p [ 5 ] = m a x ( d p [ 5 ] , 3 ∗ 2 , 3 ∗ d p [ 2 ] ) dp[5] = max( dp[5] , 3 * 2 , 3 * dp[2] ) dp[5]=max(dp[5],3∗2,3∗dp[2]) 可以得出 d p [ 5 ] > = 3 ∗ d p [ 2 ] dp[5] >= 3 * dp[2] dp[5]>=3∗dp[2],

   从而： i = 7 , j = 2 。 d p [ 7 ] = m a x ( d p [ 7 ] , 2 ∗ 5 , 6 ∗ d p [ 2 ] ) i = 7 , j = 2。dp[7] = max( dp[7] , 2 * 5, 6 * dp[2]) i=7,j=2。dp[7]=max(dp[7],2∗5,6∗dp[2])

3. 因此可以把 j 优化为 j < = i / 2 j <= i / 2 j<=i/2

class Solution {
    public int cuttingRope(int n) {
        //定义dp数组，dp[i]表示长度为i的绳子剪成m端后长度的最大乘积(m>1)
        int dp[] = new int[n + 1];
        //初始化
        dp[2] = 1;
        //目标：求出dp[n]
        //dp[2]已知，从dp[3]开始求，直到求出dp[n]
        for (int i = 3; i <= n; i++) {
            //首先对绳子剪长度为j的一段,其中取值范围为 2 <= j < i 
            //for (int j = 1; j <= i / 2; j++) 优化版本
            for (int j = 2; j < i; j++) {
                //转移方程如下
                dp[i] = Math.max(dp[i], Math.max(j * (i-j), j * dp[i-j]));
                //Math.max(j*(i-j),j*dp[i-j]是由于减去第一段长度为j的绳子后，可以继续剪也可以不剪
                //Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]))是当j不同时，求出最大的dp[i]
            }
        }
        //现在已经求出每个长度i对应的最大乘积，返回dp[n]
        return dp[n];
    }
}

方法三：递归回溯

模板：

dfs(参数) {
	if (终止条件) {
		存放结果;
		return;
	}
	
	for (选择：) {
		处理;
		dfs(); //递归
		回溯,撤销处理结果;
	}
}

class Solution {
    int res = 1;
    public int cuttingRope(int n) {
        if (n <= 3) {
            return n - 1;
        }
        dfs(2, n, 0, 1);
        return res;
    }

    public void dfs(int start, int target, int sum, int mul){
        if (sum == target && res < mul) {
            res = mul;
            return;
        }
        //优化：每一段最大长度设为3，可达到最大乘积
        //for (int i = start; i <= 3; i++)
        for (int i = start; i < target; i++){
            if (sum + i > target) {
                break;
            }
            dfs(i, target, sum + i, mul * i);
        }
    } 
}