【力扣】刷题备忘录-动归-343. 整数拆分

2023-12-11 12:36

本文主要是介绍【力扣】刷题备忘录-动归-343. 整数拆分,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

343. 整数拆分

class Solution {
public:int integerBreak(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++){ // 这里j的最大值去到i-2就可以,这时i - j = 2 正好能用初始化的值dp[i] = max(dp[i], max(j * dp[i - j], j * (i - j))); // 1. 执行拆分 有两种可能的来源 //2. 还要和dp[i]去比 然后更新// std::cout << "i的当前值是:" << i << std::endl;// std::cout << "dp i的当前值是:" << dp[i] << std::endl;}}return dp[n];}
};
  1. 这题难点在于想到 有两种可能的来源 一个是当前拆分后直接相乘的结果 另一个是拆出来的数字对应到dp table上的解相乘的结果
  2. 优化点在于想到 拆分相乘的时候j不需要去查dp[j]。
  • 至于原因,代码随想录给的是因为拆分j的情况,在遍历j = 1 to i -2 的过程中都考虑到了。
  • 我认为还有一个解释是,把这个求解过程展开,比如,dp[5] = 2 × 3, dp[6] = 3 × 3等,就会发现其实最大值都是由2 3组成的。所以把代码又优化成了下面这样:
class Solution {
public:int integerBreak(int n) {if (n <= 3) return n -1; // 这里要记得处理,不然当n<=3的时候,循环里面dp[4]取不到值 会报错vector<int> dp(n+1);dp[2] = 1;dp[3] = 2;for (int i = 4; i <= n; i++) {for (int j = 1; j <= 3; j++){  // 这里只用考虑j <= 3的情况dp[i] = max(dp[i], max(j * dp[i - j], j * (i - j))); }}return dp[n];}
};

其实分析到这里也可以写贪心了,但二刷的事情就留给二刷去做吧,这个优化方案其实已经不是动归本身了,而是基于数学做的改进了。

这篇关于【力扣】刷题备忘录-动归-343. 整数拆分的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/480710

相关文章

使用C语言实现交换整数的奇数位和偶数位

《使用C语言实现交换整数的奇数位和偶数位》在C语言中,要交换一个整数的二进制位中的奇数位和偶数位,重点需要理解位操作,当我们谈论二进制位的奇数位和偶数位时,我们是指从右到左数的位置,本文给大家介绍了使... 目录一、问题描述二、解决思路三、函数实现四、宏实现五、总结一、问题描述使用C语言代码实现:将一个整

Python实现合并与拆分多个PDF文档中的指定页

《Python实现合并与拆分多个PDF文档中的指定页》这篇文章主要为大家详细介绍了如何使用Python实现将多个PDF文档中的指定页合并生成新的PDF以及拆分PDF,感兴趣的小伙伴可以参考一下... 安装所需要的库pip install PyPDF2 -i https://pypi.tuna.tsingh

Python进行PDF文件拆分的示例详解

《Python进行PDF文件拆分的示例详解》在日常生活中,我们常常会遇到大型的PDF文件,难以发送,将PDF拆分成多个小文件是一个实用的解决方案,下面我们就来看看如何使用Python实现PDF文件拆分... 目录使用工具将PDF按页数拆分将PDF的每一页拆分为单独的文件将PDF按指定页数拆分根据页码范围拆分

PTA求一批整数中出现最多的个位数字

作者 徐镜春 单位 浙江大学 给定一批整数,分析每个整数的每一位数字,求出现次数最多的个位数字。例如给定3个整数1234、2345、3456,其中出现最多次数的数字是3和4,均出现了3次。 输入格式: 输入在第1行中给出正整数N(≤1000),在第二行中给出N个不超过整型范围的非负整数,数字间以空格分隔。 输出格式: 在一行中按格式“M: n1 n2 ...”输出,其中M是最大次数,n

整数Hash散列总结

方法:    step1  :线性探测  step2 散列   当 h(k)位置已经存储有元素的时候,依次探查(h(k)+i) mod S, i=1,2,3…,直到找到空的存储单元为止。其中,S为 数组长度。 HDU 1496   a*x1^2+b*x2^2+c*x3^2+d*x4^2=0 。 x在 [-100,100] 解的个数  const int MaxN = 3000

两数之和--力扣1

两数之和 题目思路C++代码 题目 思路 根据题目要求,元素不能重复且不需要排序,我们这里使用哈希表unordered_map。注意题目说了只对应一种答案。 所以我们在循环中,使用目标值减去当前循环的nums[i],得到差值,如果我们在map中能够找到这个差值,就说明存在两个整数的和为目标值。 如果没有找到,就将当前循环的nums[i]以及下标i放入map中,以便后续查

【每日刷题】Day113

【每日刷题】Day113 🥕个人主页:开敲🍉 🔥所属专栏:每日刷题🍍 🌼文章目录🌼 1. 91. 解码方法 - 力扣(LeetCode) 2. LCR 098. 不同路径 - 力扣(LeetCode) 3. 63. 不同路径 II - 力扣(LeetCode) 1. 91. 解码方法 - 力扣(LeetCode) //思路:动态规划。 cl

力扣第347题 前K个高频元素

前言 记录一下刷题历程 力扣第347题 前K个高频元素 前K个高频元素 原题目: 分析 我们首先使用哈希表来统计数字出现的频率,然后我们使用一个桶排序。我们首先定义一个长度为n+1的数组,对于下图这个示例就是长度为7的数组。为什么需要一个长度为n+1的数组呢?假如说总共有三个数字都为1,那么我们需要把这个1放在数组下标为3的位置,假如说数组长度为n,对于这个例子就是长度为3,那么它的

hot100刷题第1-9题,三个专题哈希,双指针,滑动窗口

求满足条件的子数组,一般是前缀和、滑动窗口,经常结合哈希表; 区间操作元素,一般是前缀和、差分数组 数组有序,更大概率会用到二分搜索 目前已经掌握一些基本套路,重零刷起leetcode hot 100, 套路题按套路来,非套路题适当参考gpt解法。 一、梦开始的地方, 两数之和 class Solution:#注意要返回的是数组下标def twoSum(self, nums: Lis

单精度浮点数按存储格式转为整数的程序

///#include<cstdio>//-----------------union int_char{unsigned char ch[4];float i;};void out_put(union int_char x)//x86是小端对其模式,即最数据的最低位存储在地址的最低位上。{printf("单精度浮点数值为:%f\n",x.i,x.i);printf("存储位置从左到右