专栏首页五分钟学算法剑指 Offer 14- I. 剪绳子

剑指 Offer 14- I. 剪绳子

大家好,我是程序员吴师兄,欢迎来到 图解剑指 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 的绳子

三、动画描述

四、图片描述

剑指 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

本文分享自微信公众号 - 五分钟学算法(CXYxiaowu),作者:程序员吴师兄

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-04-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【剑指Offer】14. 剪绳子

    尽可能多剪长度为 3 的绳子,并且不允许有长度为 1 的绳子出现。如果出现了,就从已经切好长度为 3 的绳子中拿出一段与长度为 1 的绳子重新组合,把它们切成两...

    瑞新
  • 快速拿下面试算法

    在面试前一周,我刷了很多道算法,分类刷,有些是做过的,因为我是面试C++相关岗位,除了leetcode与剑指offer相关的算法,还需要手撕一些智能指针呀,单例...

    公众号guangcity
  • 剑指offer No.67 剪绳子

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

    week
  • 剑指offer - 剪绳子 II - JavaScript

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

    心谭博客
  • Python 剪绳子的多种思路实现(动态规划和贪心)

    题:给你一根长度为n的绳子,请把绳子剪成m段(m,n都是整数,且n 1,m 1),每段绳子的长度记为k[0],k[1],k[2],…,k[m]。请问k[0]*k...

    砸漏
  • 剑指offer_14_剪绳子

    动态规划:当绳子长度为n时,我们剪第一刀有n-1种可能,因为第一刀可以剪1米、2米、3米....n-1米。因此f(n) = max(f(i) * f(n - i...

    用户6055494
  • LeetCode 343. 整数拆分(DP)

    给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

    Michael阿明
  • 【Python】剑指offer 14:剪

    题目:给你一根长度为n的绳子,请把绳子剪成m段 (m和n都是整数,n>1并且m>1)每段绳子的长度记为k[0],k[1],…,k[m].请问k[0]k[1]…*...

    py3study
  • 数学题:查找,快速幂,二进制,剪绳子

    各位小伙伴,又到周末啦~本周小白已经开始二刷《剑指offer》了,这次在LeetCode上面刷题,发现LeetCode上面的《剑指offer》和牛客上面的题目好...

    鹏-程-万-里
  • 剑指offer(61-67)题解

    例如,我们可以把一个只有根节点为1的二叉树序列化为"1,",然后通过自己的函数来解析回这个二叉树

    萌萌哒的瓤瓤
  • Day68:剑指Offer总结

      本人花了两个月时间刷完了牛客网带上的剑指Offer,一共67题。本人是从4月21日开始刷题,每天一题,截止到7月6日已经全部刷完。这67题均是考察的数据结构...

    一计之长
  • Day67:剪绳子

    背景知识介绍:   在做题之前,首先给大家介绍数据结构中典型的贪心算法以及动态规划。在维基百科中是这样介绍贪心算法和动态规划的。贪心算法(greedy alg...

    一计之长
  • 【刷题】2020最新剑指Offer汇总

    新手村 关卡1-1 洛谷的第一个任务 P1000 超级玛丽游戏:点击这里 P1001 A+B Problem:点击这里 P1421 小玉买文具:点击这里...

    瑞新
  • 【好书推荐】《剑指Offer》之硬技能(编程题12~16)

    题目:请设计一个函数,用来判断一个矩阵中是否存在一条包含其字符串所有字符的路径。路径可以从矩阵中的任意一格开始,每一步可以在矩阵中向左、右、上、下移动一格。如果...

    用户1148394
  • 剑指 Offer(C++版本)系列:剑指 Offer 13 机器人的运动范围

    同步GitHub在此 ? https://github.com/TeFuirnever/GXL-Skill-Tree

    我是管小亮
  • 剑指 Offer(C++版本)系列:剑指 Offer 10- I 斐波那契数列

    同步GitHub在此 ? https://github.com/TeFuirnever/GXL-Skill-Tree

    我是管小亮
  • 《剑指 offer》刷题记录之:动态规划与贪婪算法

    动态规划是编程面试中的热门话题。一般来说,能够用动态规划求解的问题具有如下三个特点:

    口仆
  • 剑指 Offer(C++版本)系列:剑指 Offer 07 重建二叉树

    同步GitHub在此 ? https://github.com/TeFuirnever/GXL-Skill-Tree

    我是管小亮
  • 回溯法思想(剑指Offer 65/66)

    请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个...

    算法工程师之路

扫码关注云+社区

领取腾讯云代金券