难度**

中等

思路

递归思想

• 递推式 F(n) = Max(i*(n-i), i * F(n-i))
• i*(n-i) 表示当前绳子由 i 和 n-i 两部分构成，且都不可继续拆分。
• i*F(n-i) 表示当前绳子由 i和 n-i 两部分构成，而 n-i 部分可以继续拆分。

/**
 * 递归: F(n) = Max(i*(n-i), i*F(n-i))
 */
public static int cuttingRope_1(int n) {
    if (n == 2) {
        return 1;
    }
    int ret = -1;
    for (int i = 1; i < n; i++) {
        ret = Math.max(ret, Math.max(i * (n - i), i * cuttingRope_1(n - i)));
    }
    return ret;
}

动态规划

• dp[n] = Max(dp[n], Max(i*(n-i), i * dp[n-i])); 左边表示绳子可以不用在切，而 Max(i*(n-i), i*dp[n-i]) 表示切成 i 长度，剩下的 n-i 需要继续切。
• 上述动态规划式最重要的是融入 i 这个变量，这在编程中也需要考虑如何引入这个变量，需要对此变量有一个深刻的认知。实际中，i 是一个循环变量，有 0<i<n，表示从 0~n 尝试切割，再比较两者之间谁大谁小。

  public static int cuttingRope_3(int n) {
    int[] dp = new int[n + 1];
    dp[2] = 1;
    for (int i = 3; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            System.out.println(String.format("i:%s, j:%s, dp[i]:%s", i, j, dp[i]));
        }
    }
    return dp[n];
  }

  | 时间复杂度 | O(2__) | | —- | —- | | 空间复杂度 | O(n) |

总结

• 递归是从上往下，因此，会有很多重复计算，而动态规划是从下往上，使用一个数组存储值，因此避免了重复计算开销。
• 而动态规划的递推式是比较难想到的，需要做大量的题目才能了解。