剑指 Offer 14- I:剪绳子

简介: 剑指 Offer 14- I:剪绳子

题目

题目链接

给你一根长度为 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

解题

此题和leetcode-343:整数拆分是一样的

方法一:动态规划

class Solution {
public:
    int cuttingRope(int n) {
        vector<int> dp(n+1);
        dp[2]=1;
        for(int i=3;i<=n;i++){
            for(int j=1;j<i-1;j++){
                dp[i]=max({dp[i],j*(i-j),j*dp[i-j]});
            }
        }
        return dp[n];
    }
};
相关文章
|
27天前
|
人工智能 算法 BI
AcWing 505. 火柴排队(每日一题)
AcWing 505. 火柴排队(每日一题)
|
算法
【学会动态规划】剑指 Offer II 091. 粉刷房子(14)
【学会动态规划】剑指 Offer II 091. 粉刷房子(14)
47 0
|
6月前
剑指 Offer 14- II:剪绳子 II
剑指 Offer 14- II:剪绳子 II
31 0
|
算法
【算法挨揍日记】day04——15. 三数之和、18. 四数之和
题目描述: 给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
75 0
|
存储 测试技术
LeetCode 周赛 352(2023/07/02)一场关于子数组的专题周赛
往期回顾:[LeetCode 单周赛第 350 场 · 滑动窗口与离散化模板题](https://mp.weixin.qq.com/s/7_neqKFSRMANFTxtVj64gA)
42 0
LeetCode 周赛 352(2023/07/02)一场关于子数组的专题周赛
|
算法 Android开发 容器
LeetCode 周赛上分之旅 #35 两题坐牢,菜鸡现出原形
学习数据结构与算法的关键在于掌握问题背后的算法思维框架,你的思考越抽象,它能覆盖的问题域就越广,理解难度也更复杂。在这个专栏里,小彭与你分享每场 LeetCode 周赛的解题报告,一起体会上分之旅。
89 0
|
存储
剑指Offer - 面试题14:剪绳子
剑指Offer - 面试题14:剪绳子
81 0
|
机器学习/深度学习
剑指offer 13. 剪绳子
剑指offer 13. 剪绳子
71 0
|
Java Python
【LeetCode每日一题】剑指 Offer 14- II. 剪绳子 II(持续更新)
【LeetCode每日一题】剑指 Offer 14- II. 剪绳子 II(持续更新)
72 0
|
Java Python
【LeetCode每日一题】剑指 Offer 14- I. 剪绳子(持续更新)
【LeetCode每日一题】剑指 Offer 14- I. 剪绳子(持续更新)
51 0