大家好,我是程序员吴师兄,欢迎来到 图解剑指 Offer 结构化专栏,在这个专栏里我将和大家一起学习如何用结构化的思维来思考、解题、写代码,希望能帮助你即使在面试的时候紧张也能做对。


今天分享的题目来源于 LeetCode 上的剑指 Offer 系列 面试题 14-I. 剪绳子

题目汇总链接:https://www.algomooc.com/jianzhioffer

一、题目描述

给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1并且m>1),每段绳子的长度记为 k[0],k[1]...k[m-1]

请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少?

例如,当绳子的长度是 8 时,我们把它剪成长度分别为 2、3、3 的三段,此时得到的最大乘积是 18

示例 1:

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

提示:

  • 2 <= n <= 58

二、题目解析

我们依旧用 四步分析法 进行结构化的分析,帮助我们思考和发现规律,写出合理的代码。

  • 模拟:模拟题目的运行。
  • 规律:尝试总结出题目的一般规律和特点。
  • 匹配:找到符合这些特点的数据结构与算法。
  • 边界:考虑特殊情况。

1、模拟

我们假设绳子的长度为 10。

剑指 Offer 14- I. 剪绳子.002

先来剪一下,假设一开始剪下来的长度为 1,那么左边绳子的长度为 1,右边绳子的长度为 9,它们的乘积为 1 * 9 = 9

对于一段一开始长度为 10 的绳子而言,9 是小于 10 的,因此剪下长度为 1 的绳子是无法增大乘积的,更一般的来说,1 和任何数相乘都是那个数本身,因此对于任意长度的绳子来说都不应该剪长度为 1 的绳子下来

数学证明:n > ( n - 1) * 1

剑指 Offer 14- I. 剪绳子.003

所以,每次剪绳子的操作都是剪至少长度为 2 的绳子的操作。

剑指 Offer 14- I. 剪绳子.005

当剪下一段长度为 2 的绳子时,剩下的绳子长度为 8。

那么对于长度为 8 的这段绳子来说,它有两个选择,剪或者不剪。

  • 不剪,乘积结果为 2 * 8 = 16
  • 剪,怎么剪?

对于这两个选择,我们无法第一时间做出决定,因为目前还不知道剪的情况下能否出现大于 16 的结果。

剑指 Offer 14- I. 剪绳子.007

所以,接下来的操作就是去剪第二段绳子。

怎么剪呢?

和剪长度为 10 的那段绳子一样的思路。

剑指 Offer 14- I. 剪绳子.012

剪完之后,第二段绳子也被划分两块区域,a 和 b。

剑指 Offer 14- I. 剪绳子.013

通过剪长度为 10 的绳子与长度为 8 的绳子的操作,我们可以发现:我们在不停的去剪相对的那根 第二段 的绳子,直到剪无可剪为止。

剑指 Offer 14- I. 剪绳子.016

此时我们考虑第二段的情况时,第一段绳子的长度为 2,而事实上,第一段绳子可取的范围为 [ 2,i)。

假设当下绳子的长度为 i

剑指 Offer 14- I. 剪绳子.020

剑指 Offer 14- I. 剪绳子.026

2、规律

长度为 n 的绳子剪掉后的最大乘积与求绳子长度为 n - 1n - 2n - 3 的最大乘积求法一样。

不会剪长度为 1 的绳子下来。

剑指 Offer 14- I. 剪绳子.028

假设剪的绳子那段称为 第一段,剪剩下的那段绳子称为 第二段,那么第一段的范围为 [2,i),第二段可以剪或者不剪,假设 dp[i] 表示长度为 i 的绳子剪成 m 段后的最大乘积,那么,不剪总长度乘积为 j * ( i - j),剪的话长度乘积为 j * dp[ i - j ],取两者的最大值,即 Max ( j * ( i - j) , j * dp[ i - j] )

3、匹配

通过规律可以发现,本题具备以下几个特征:

  • (1)是求最优解问题,如最大值,最小值;
  • (2)该问题能够分解成若干个子问题,并且子问题之间有重叠的更小子问题。

动态规划

状态dp[i]

状态转移方程dp[i] = Max(dp[i], Max(j * (i - j), j * dp[i - j]))

4、边界

  • 长度为 1 的绳子
  • 长度为 2 的绳子

三、动画描述

隐藏内容
  • 普通用户购买价格:5积分
  • 会员用户购买价格:免费
  • 永久会员用户购买价格:免费推荐

四、图片描述

剑指 Offer 14- I. 剪绳子.002

剑指 Offer 14- I. 剪绳子.003

剑指 Offer 14- I. 剪绳子.004

剑指 Offer 14- I. 剪绳子.005

剑指 Offer 14- I. 剪绳子.006

剑指 Offer 14- I. 剪绳子.007

剑指 Offer 14- I. 剪绳子.008

剑指 Offer 14- I. 剪绳子.009

剑指 Offer 14- I. 剪绳子.010

剑指 Offer 14- I. 剪绳子.011

剑指 Offer 14- I. 剪绳子.012

剑指 Offer 14- I. 剪绳子.013

剑指 Offer 14- I. 剪绳子.014

剑指 Offer 14- I. 剪绳子.015

剑指 Offer 14- I. 剪绳子.016

剑指 Offer 14- I. 剪绳子.017

剑指 Offer 14- I. 剪绳子.018

剑指 Offer 14- I. 剪绳子.019

剑指 Offer 14- I. 剪绳子.020

剑指 Offer 14- I. 剪绳子.021

剑指 Offer 14- I. 剪绳子.022

剑指 Offer 14- I. 剪绳子.023

剑指 Offer 14- I. 剪绳子.024

剑指 Offer 14- I. 剪绳子.025

剑指 Offer 14- I. 剪绳子.026

剑指 Offer 14- I. 剪绳子.027

剑指 Offer 14- I. 剪绳子.028

剑指 Offer 14- I. 剪绳子.029

剑指 Offer 14- I. 剪绳子.030

剑指 Offer 14- I. 剪绳子.031

剑指 Offer 14- I. 剪绳子.032

五、参考代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
class Solution {
    public int cuttingRope(int n) {
        // 长度为 1 的绳子没法剪了
        if ( n <= 1 ) return 1;
        // 用一个名为 dp 的数组来记录从 0 到 n 长度的绳子剪掉后的最大乘积
        // 默认都是 0
        int[] dp = new int[n + 1];
        // 由于绳子必须被剪,所以长度为 2 的绳子只有剪成 1 和 1 的两段,乘积结果为 1
        dp[2] = 1;
        // 长度大于等于 3 的绳子才开始进入我们的讨论范围
        // 从长度为 3 的绳子开始考虑,讨论它的最大乘积是多少,并不断的延伸绳子的长度
        for(int i = 3; i < n + 1; i++){
            // 对于长度为 i 的绳子,它可以分为两个区间 j 和 i - j
            // j 的范围由 2 开始,因为剪长度为 1 的绳子无法扩大乘积的值
            // j 的范围可以延伸至 i - 1
            for(int j = 2; j < i; j++){
                // 不剪总长度乘积为  j * ( i - j)
                // 剪的话长度乘积为  j * dp[ i - j ]
                // 取两者的最大值,即  Max ( j * ( i - j) , j * dp[ i - j] )
                // 那么此时 dp[i] 的值取 i 不剪的值( dp[i]) 和剪的值 Math.max(j * (i - j), j * dp[i - j]) 这两者的最大值
                // 比如一开始 i = 3 , j = 2
                // dp[3] = Math.max( 0 ,Math.max ( 2 * 1, 2 * dp[1])
                //       = Math.max( 0 ,Math.max ( 2, 2))
                //       = 2
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }
}

六、复杂度分析

时间复杂度

时间复杂度为 O(n2) 。

空间复杂度

空间复杂度为 O(n) 。

七、相关标签

  • 动态规划
  • 数学

八、参考链接

1、https://leetcode-cn.com/problems/jian-sheng-zi-lcof/

2、https://www.algomooc.com/jianzhioffer

发表评论

邮箱地址不会被公开。 必填项已用*标注