剑指 Offer 14- I. 剪绳子
14 Offer
2023-09-11 14:19:00 时间
思路
方法一:动态规划
从题目中可以看出,有最优子结构,可以联想到动态规划,其递归树如下:
可以看出,具有很多重叠子问题。
1 /*记忆化搜索代码*/ 2 class Solution { 3 private: 4 // 记忆化搜索,自顶向下 5 // memo[n]表示分割n获得的乘积最大值 6 vector<int> memo; 7 int max3(int a, int b, int c) { 8 return max(a, max(b,c)); 9 } 10 int breakInteger(int n) { 11 if(n == 1) 12 return 1; 13 14 if(memo[n] != -1) 15 return memo[n]; 16 17 int res = -1; 18 for(int i = 1; i < n; ++i) { 19 res = max3(res, i*(n-i), i * breakInteger(n-i)); 20 } 21 memo[n] = res; 22 return memo[n]; 23 24 } 25 public: 26 int integerBreak(int n) { 27 memo = vector<int>(n+1, -1); 28 return breakInteger(n); 29 } 30 }; 31 32 /*动态规划代码*/ 33 class Solution { 34 private: 35 // 动态规划,自底向上 36 // 求三个数中的最大值 37 int max3(int a, int b, int c) { 38 return max(a, max(b,c)); 39 } 40 41 public: 42 int integerBreak(int n) { 43 vector<int> memo(n+1, -1); 44 // memo[i]表示分割i获得的乘积最大值 45 // 题目中说了n>=2,所以这里不能写memo[3]=2,否则当输入的n是2时会越界 46 memo[1] = 1; 47 memo[2] = 1; 48 for(int i = 3; i <= n; ++i) { 49 for(int j = 1; j < i; ++j) { 50 memo[i] = max3(memo[i], j*(i-j), j*memo[i-j]); 51 } 52 } 53 return memo[n]; 54 } 55 };
复杂度分析
记忆化搜索:
时间复杂度:O(n2),因为breakInteger递归函数中有一个n次循环,每个memo[i]的值只会被计算一次,不会重复递归计算相同的memo[i] (因为相同的直接返回了),所以时间复杂度为O(n2)
空间复杂度:O(n)
动态规划:
时间复杂度:O(n2)
空间复杂度:O(n)
方法二:数学
以下证明来自:《剑指offer(第2版)》,面试题14- I. 剪绳子(数学推导 / 贪心思想,清晰图解)
更详细的数学证明见:力扣官方题解 - 整数拆分
1 class Solution { 2 public: 3 int cuttingRope(int n) { 4 if(n <= 3) 5 return n-1; 6 int res = 1; 7 while(n > 4) 8 { 9 n = n - 3; //尽可能地多剪长度为3的绳子 10 res = res * 3; 11 } 12 return res * n; 13 } 14 };
参考
相关文章
- 《惢客创业日记》2021.06.13-14(周日)茶领域如何证明诚信?
- 《惢客创业日记》2019.08.14(周三) 谁说中医没有量化?(五)
- 14.parfor并行循环处理
- 数仓工具—Hive架构之HiveServer2(14)
- JavaScript 即未来:介绍 14 个 JavaScript 的框架和库
- 博客新功能上线,可导出PDF……【2021.12.14】
- 14 Lock(锁)代码:测试Lock锁 synchronized与Lock的对比
- 《社会调查数据管理——基于Stata 14管理CGSS数据》一1.2 数据管理内容不清
- 《社会调查数据管理——基于Stata 14管理CGSS数据》一2.3 数据管理的工作规范
- 《社会调查数据管理——基于Stata 14管理CGSS数据》一3.5 中国综合社会调查
- 14个Xcode中常用的快捷键操作
- 2014第14周二
- SwiftUI 动态岛开发教程之02 iPhone 14 Pro 如何使用 Dynamic Island
- Vue知识点总结(14)——其它组件通信方式(provide/inject和$parent/$children)(超级详细)
- 2021-10-14
- 【历史上的今天】9 月 14 日:中国第一封电子邮件;世界上最早的电子银行系统;微软发布 Windows Me
- 思科14亿美元收购物联网公司Jasper