【LeetCode343】剪绳子(动态规划)

简介: (1)确定状态dp[i]是将正整数i拆成2个及其以上的正整数后,求所有数的乘积值。

一、题目

image.png

二、思路

(1)确定状态

dp[i]是将正整数i拆成2个及其以上的正整数后,求所有数的乘积值。


(2)状态转移方程

当 i≥2 时,假设对正整数 i 拆分出的第一个正整数是 j(1≤j<i),则有以下两种方案:

1)将 i 拆分成 j 和 i−j 的和,且 i−j 不再拆分成多个正整数,此时的乘积是 j×(i−j);

2)将 i 拆分成 j 和 i−j 的和,且 i−j 继续拆分成多个正整数,此时的乘积是 j×dp[i−j]。

因此,当 j 固定时,有

image.png

最终得到 dp[n] 的值即为将正整数 n 拆分成至少两个正整数的和之后,这些正整数的最大乘积。

(3)边界+初始条件

边界条件: 0 不是正整数,1 是最小的正整数,0 和 1 都不能拆分,因此 dp[0]=dp[1]=0。

(4)计算顺序

从小到大。

三、C++代码

class Solution {
public:
    int cuttingRope(int n) {
        vector<int>dp(n + 1);
        for(int i = 2; i <= n; i++){
            for(int j = 1; j < i; j++){
                dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }
};
相关文章
|
5月前
|
机器学习/深度学习 算法 Go
【LeetCode 热题100】139:单词拆分(动态规划全解析+细节陷阱)(Go语言版)
本题是 LeetCode 热题 139:单词拆分(Word Break),需判断字符串 `s` 是否能由字典 `wordDict` 中的单词拼接而成。通过动态规划(DP)或记忆化搜索解决。DP 中定义布尔数组 `dp[i]` 表示前 `i` 个字符是否可拆分,状态转移方程为:若存在 `j` 使 `dp[j]=true` 且 `s[j:i]` 在字典中,则 `dp[i]=true`。初始条件 `dp[0]=true`。代码实现中用哈希集合优化查找效率。记忆化搜索则从起始位置递归尝试所有切割点。两种方法各有利弊,DP 更适合面试场景。思考扩展包括输出所有拆分方式及使用 Trie 优化大字典查找。
146 6
|
机器学习/深度学习 存储 算法
LeetCode 题目 95:从递归到动态规划实现 不同的二叉搜索树 II
LeetCode 题目 95:从递归到动态规划实现 不同的二叉搜索树 II
|
缓存
力扣每日一题 6/14 动态规划+数组
力扣每日一题 6/14 动态规划+数组
95 1
|
算法 数据挖掘 开发者
LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
|
存储 算法 数据可视化
深入解析力扣161题:相隔为 1 的编辑距离(逐字符比较与动态规划详解)
深入解析力扣161题:相隔为 1 的编辑距离(逐字符比较与动态规划详解)
|
存储 算法 数据可视化
LeetCode 题目 96:从动态规划、递归到卡塔兰数实现不同的二叉搜索树
LeetCode 题目 96:从动态规划、递归到卡塔兰数实现不同的二叉搜索树
|
存储 算法 数据可视化
LeetCode 132题详解:使用动态规划与中心扩展法解决分割回文串 II 的最少分割次数问题
LeetCode 132题详解:使用动态规划与中心扩展法解决分割回文串 II 的最少分割次数问题
|
存储 算法 数据可视化
LeetCode 131题详解:高效分割回文串的递归与动态规划方法
LeetCode 131题详解:高效分割回文串的递归与动态规划方法
|
存储 SQL 算法
优化解码方法:记忆化搜索和空间优化动态规划的实用指南 【LeetCode 题目 91】
优化解码方法:记忆化搜索和空间优化动态规划的实用指南 【LeetCode 题目 91】
|
算法 索引
力扣每日一题 6/28 动态规划/数组
力扣每日一题 6/28 动态规划/数组
112 0