当前位置:网站首页>七夕力扣刷不停,343. 整数拆分(剑指 Offer 14- I. 剪绳子、剑指 Offer 14- II. 剪绳子 II)
七夕力扣刷不停,343. 整数拆分(剑指 Offer 14- I. 剪绳子、剑指 Offer 14- II. 剪绳子 II)
2022-08-09 12:46:00 【byte字节8位-128~127】
https://leetcode-cn.com/problems/integer-break/
https://leetcode-cn.com/problems/jian-sheng-zi-lcof/
根据以上思路得动态规划状态转移方程dp表达式
dp[n] = max(dp[n],dp[j]*dp[n-j]);
这里解释一下,就是可以选择直接是dp[n],或者将dp[n]划分为两个数,看这两个数的乘积和不划分的dp[n],这两个哪个比较大。
有时候划分了可能会变小,比如dp[2],dp[3]
dp6中可能包括多个dp[2]或者3,所以,这个时候就要考虑,是否要继续划分的问题。
dp[n]:长度为n的数获得的乘积的最大值
class Solution {
public int integerBreak(int n) {
//动态规划
//base case
int[] dp = new int[n+1];
if(n<2){
return 1;
}
if(n==2){
return 1;
}
if(n==3){
return 2;
}
//这里要说明一下,因为对于2、3,再拆分就会越来越小,
//所以就不拆分了,只要答案对就行,也不能太纠结
dp[1]=1;
dp[2]=2;
dp[3]=3;
//双层for循环,动态规划经典标志
for(int i=4;i<=n;i++){
for(int j=1;j<=(i/2);j++){
dp[i] = Math.max(dp[i],dp[j]*dp[i-j]);
}
}
return dp[n];
}
}
class Solution {
public int integerBreak(int n) {
if(n<=2){
return 1;
}
if(n==3){
return 2;
}
int[] dp = new int[n+1];
//基础的就不分了,因为会越分越小
dp[1]=1;dp[2]=2;dp[3]=3;
// dp[1]=1;
// dp[2]=2;
// dp[3]=3;
for(int i=4;i<=n;i++){
for(int j=1;j<=(i/2);j++){
dp[i] = Math.max(dp[i],dp[j]*dp[i-j]);
}
}
return dp[n];
}
}
代码一样,只是出现了一个bug,调试一下,就好了
class Solution {
public int cuttingRope(int n) {
int[] dp = new int[n+1];
if(n<=2){
return 1;
}
if(n==3){
return 2;
}
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
//双层for循环,经典动态规划标志
for(int i=4;i<=n;i++){
//这里的j忘记写=了
for(int j=1;j<=(i/2);j++){
System.out.println(dp[i]);
System.out.println(dp[j]*dp[i-j]);
dp[i] = Math.max(dp[i],dp[j]*dp[i-j]);
System.out.println(dp[i]);
}
}
return dp[n];
}
}
剑指 Offer 14- II. 剪绳子 II
https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof/solution/wu-xu-fu-za-shu-xue-jiang-jie-dong-tai-g-j470/
class Solution {
public:
int cuttingRope(int n) {
if (n < 4) {
return n - 1;
}
vector<int> products(n + 1, 0);
products[1] = 1;
products[2] = 2;
products[3] = 3;
int maxVal = 0;
for (int i = 4; i <= n; ++i) {
maxVal = 0;
for (int j = 1; j <= i / 2; ++j) {
maxVal = max(maxVal, products[j] * products[i - j]);
}
products[i] = maxVal;
}
return products[n];
}
};
class Solution {
public int cuttingRope(int n) {
/** 思路:动态规划 费曼学习法一遍 动态规划是一种穷举,然后可以避免我们重复计算 我们先自上而下考虑: 比如,对于一个绳子n,我们可以先切一刀 然后,获取两段,那么我们可以有n-1种切法,因为n要求是整数 然后可以对其中一段,再进行切 获取若干段,不断重复这个过程 最后直到分为不可以再分的段数,然后我们 再自下而上的考虑: 然后根据求出的每段的最大值,来考虑该段是否需要进行划分 由于有一些边界条件限制,所以我们应该先初始化 */
if(n<2){
return 1;
}
if(n==2){
return 1;
}
if(n==3){
return 2;
}
int[] dp = new int[n+1];
//由公式可以证明,当n小于4的时候,不分开获取的结果会更大一些
//我们的dp数组,就是按照不分开进行计算的
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
//穷举每一种可能
for(int i=4;i<=n;i++){
//每一种可能是否需要划分
for(int j=1;j<=(i/2);j++){
//是否划分,划分后大还是不划分大,整一个for循环,来寻找dp[i]的最大值
dp[i] = Math.max(dp[i],dp[j]*dp[i-j]);
}
}
return dp[n];
}
}
边栏推荐
- JVM内存泄漏和内存溢出的原因
- Clock frequency and baud rate count for serial communication in FPGA
- 史上最猛“员工”,疯狂吐槽亿万富翁老板小扎:那么有钱,还总穿着同样的衣服!...
- 二维数组&指针
- Compensation transaction and idempotency guarantee based on CAP components
- ERP不规范,同事两行泪 (转载非原创)
- 5G China unicom 一般性异常处理
- Fragment中嵌套ViewPager数据空白页异常问题分析
- MySQL5.6到8.0的账号迁移
- 注:检测到当前使用的ADB不是HBuilder内置或自定义ADB:PID为:9544进程名称为:adb.exe 路径为:c:\users\administrator\appdata\local\and
猜你喜欢
绘制混合密度函数图以及添加分位数线
ctfshow七夕杯2022
Anta and Huawei Sports Health jointly verify the champion running shoes and lead Chinese sports with innovation
我的2020年终总结
ViewPager fragments of nested data blank page abnormal problem analysis
乐东消防救援大队应邀为干部开展消防安全培训
26. Pipeline parameter substitution command xargs
RTSP协议讲解
The FPGA - work summary recently
Flutter Getting Started and Advanced Tour (4) Text Input Widget TextField
随机推荐
ansible-cmdb friendly display ansible collects host information
Fragment中嵌套ViewPager数据空白页异常问题分析
卷积神经网络表征可视化研究综述(1)
Flutter入门进阶之旅(十)Dialog&Toast
R语言kaggle 游戏数据探索与可视化
Flutter入门进阶之旅(四)文本输入Widget TextField
jenkins api创建自定义pipeline
如何求最大公约数?
陈强教授《机器学习及R应用》课程 第十三章作业
FFmpeg多媒体文件处理(ffmpeg处理流数据的基本概念)
Rust 入门指南(使用JSON)
NFS pays special attention to the problem of permissions
流量焦虑背后是企业对客户关系管理的不足
glide工具类的简单封装
ARM板卡增加路由功能
GIN Bind模式获取参数和表单验证
Redis源码剖析之跳表(skiplist)
5G China unicom AP:B SMS ASCII Transcoding Requirements
Ten minutes to teach you how to use VitePress to build and deploy a personal blog site
【FPGA教程案例48】图像案例8——基于FPGA的RGB图像转化为HSV图像的实现,通过MATLAB进行辅助验证