首页 > 其他分享 >343. 整数拆分(leetcode)

343. 整数拆分(leetcode)

时间:2024-08-31 23:14:23浏览次数:7  
标签:cn int 整数 拆分 343 leetcode

https://leetcode.cn/problems/integer-break/

dp,思路较为巧妙,需要考虑一个数至少能拆成两份这个点,且需要考虑到拆的这个数的值域是多少(1,i-1)
且选择拆一次还是拆多次

class Solution {
public:
    int integerBreak(int n) {
        // f[i]表示拆分i成若干个整数的最大乘积
        // f[i] = max(j*(i-j),j*f[i-j])
        // f[2]=1;
        const int N = 60;
        int f[N];
        memset(f,0,sizeof f);
        f[2]=1;
        for(int i=3;i<=n;i++)
            for(int j=1;j<i;j++)
                f[i]=max(f[i],max(j*(i-j),j*f[i-j]));
        return f[n];
    }
};

 

标签:cn,int,整数,拆分,343,leetcode
From: https://www.cnblogs.com/lxl-233/p/18390909

相关文章

  • 63. 不同路径 II(leetcode)
    简单dphttps://leetcode.cn/problems/unique-paths-ii/description/传统做法:classSolution{public:intuniquePathsWithObstacles(vector<vector<int>>&obstacleGrid){intf[110]={0};//优化一维f[1]=1;intm=obstacleGrid......
  • 数据结构:(LeetCode965)单值二叉树
     一:定义如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树。只有给定的树是单值二叉树时,才返回 true;否则返回false。示例1:输入:[1,1,1,1,1,null,1]输出:true示例2:输入:[2,2,2,5,2]输出:false 提示:给定树的节点数范围是 [1,100]。每个节点的值都是......
  • 数据结构:(LeetCode 965)相同的树
    给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。示例1:输入:p=[1,2,3],q=[1,2,3]输出:true示例2:输入:p=[1,2],q=[1,null,2]输出:false示例3:输入:p=[1,2,1]......
  • leetcode刷题day4|链表部分(24. 两两交换链表中的节点 、19.删除链表的倒数第N个节点、
    前言:链表练习的第二天,对链表的理解加深了24.两两交换链表中的节点这个题一开始的思路是用cur和next两个指针来做,但是绕来绕去绕迷糊了,最后超时了。把错误的代码放在下面警醒大家:主要问题出现在这两行代码,next.next发生了更改。next.next=next.next.next;next.next.nex......
  • leetcode刷题day3|链表部分( 203.移除链表元素、707.设计链表、206.反转链表)
    前言:链表部分之前刷过一些题,掌握的还可以,希望可以顺利把这部分题刷完。203.移除链表元素思路:自己创建一个头节点,使新的头节点指向旧的头节点。错误尝试:一开始考虑的比较复杂,设置了指针pre,能够想到直接比较cur.next.val和val的值会使代码更加简洁,但也要注意想清楚如果删除......
  • 【每日一题】LeetCode 1343.大小为K且平均值大于等于阈值的子数组数目(数组、滑动窗口)
    【每日一题】LeetCode1343.大小为K且平均值大于等于阈值的子数组数目(数组、滑动窗口)题目描述给定一个整数数组arr和两个整数k和threshold,要求找出数组中长度为k且平均值大于等于threshold的子数组的数量。输入格式arr:一个整数数组。k:子数组的长度。thres......
  • leetcode 3 无重复字符最长串
    leetcode3无重复字符最长串思路使用滑动窗口,建两个整型变量lp和rp,分别代表左边界指针和右边界指针,整型temp储存当前字串长度,整形max储存当前最长长度,然后从左往右遍历字符串。解题过程先将字符串toCharArray转成字符数组m,建一个哈希集合,储存当前已经用过的字符,然后写一......
  • LeetCode题集-1- 两数之和
      这个题目是什么意思呢?简单来说就是在一个数组中找出两个元素,使其和为我们设定的值,并且每个元素只能用一次。 如下图具体示例: 到这里不知道你是否已经有解题思路了呢?解法一:双层循环我第一反应就是双层循环,直接暴力破解。因为题目要求每个元素只能使用一次,并且已经计......
  • LeetCode 热题 100 回顾
    目录一、哈希部分1.两数之和 (简单)2.字母异位词分组 (中等)3.最长连续序列 (中等)二、双指针部分4.移动零 (简单)5.盛最多水的容器 (中等)6. 三数之和 (中等)7.接雨水 (困难)三、滑动窗口8.无重复字符的最长子串 (中等)9.找到字符串中所有字母异位词 (中等)四、子串10.......
  • 738. 单调递增的数字(leetcode)
    https://leetcode.cn/problems/monotone-increasing-digits/description/classSolution{publicintmonotoneIncreasingDigits(intn){//返回单调递增的最大数字//思路比较巧妙的贪心题,需要仔细考虑两个相邻位之间的比较//一旦发现有前一......