大数据平台 centos7安装 canal安装 海思 vcpkg routes ionic3 vue组件开发 nginx视频 android项目实例 etc文件夹 c语言求和 maven配置eclipse pip环境变量 安卓虚拟机运行windows axure导出html文件 kubernetes入门 python注释 python加法 python算法 javapackage java字符串长度 java中的正则表达式 jdbc连接mysql java删除文件 java的框架 java异常处理 java注释规范 java语言运算符 js倒计时代码 r语言和python 卡巴斯基离线升级包 烧饼修改器打不开 js分页 mac强制重启 python数组赋值 光头强换肤助手 草图大师版本转换器 暗黑3挂机plusready studioone
当前位置: 首页 > 学习教程  > 编程语言

343. 整数拆分

2020/11/4 14:05:29 文章标签:

给定一个正整数 n&#xff0c;将其拆分为至少两个正整数的和&#xff0c;并使这些整数的乘积最大化。 返回你可以获得的最大乘积。 示例 1: 输入: 2 输出: 1 解释: 2 1 1, 1 1 1。 另dp[i]表示正整数i的最大乘积 把i拆分为i-jji&#xff0c;j<(i-1)&#xff0c;因为…

给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

示例 1:

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

另dp[i]表示正整数i的最大乘积

把i拆分为i-j+j=i,j<=(i-1),因为如果j大于等于i那么乘积就不是正整数了,那么(i-j) * j

如果再把(i-j)也拆开,对应的乘积就是dp[i-j]*j

两个取最大值

class Solution {
public:
    int integerBreak(int n) {
        int *dp = new int[n + 1]();
        dp[1] = 1;
        for(int i = 2; i <= n; i++)
        {
            for(int j = 1; j < i; j++)
                dp[i] = max(dp[i], max(dp[i-j]*j, (i-j)*j));
        }
        return dp[n];
    }
};

 


本文链接: http://www.dtmao.cc/news_show_350065.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?