LeetCode剑指Offer 14-I剪绳子(Java)

文章目录

• LeetCode - 剑指 Offer 14- I: 剪绳子 (Java)
• 第一部分为题目
• 第二部分阐述解题思路
• • 1. 动态规划法
    • 采用动态规划法求解最优子结构
    • 计算所有可能的子问题并记录结果以避免重复计算
    • 最终通过状态转移方程获得全局最优解
• • 2. 贪心算法

    • 应用贪心算法选择局部最优策略以达到全局最优效果

    • 每一步都做出当前看似最佳的选择以逐步逼近最终目标

    • 这种方法通常适用于具有贪心性质的问题场景中

    • 三、代码

    • • 3.1 动态规划1
      • 3.2 动态规划2
      • 3.3 贪婪算法

LeetCode 之 剑指 Offer 14- I. 剪绳子 （Java）

一、题目

剑指 Offer 14- I. 剪绳子

给定一根长度为n的绳子，请将其分成m个整数长度的部分（其中m和n均为大于1的整数），设各部分长度依次为k_0, k_1, ..., k_{m-1}。那么这些段的最大乘积可能是多少？例如，在n=8的情况下…

示例 1：

    输入: 2
    输出: 1
    解释