您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

java leetcode之[动态规划]343. 整数拆分

题目的链接在这里:https://leetcode-cn.com/problems/integer-break/

目录

  • 题目大意
  • 一、示意图
  • 二、解题思路
    • 动态规划


题目大意

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

一、示意图

在这里插入图片描述

二、解题思路

//如果是动态规划的话 那只能是dp[n]=max(dp[n-1]*1,dp[n-2]*2)..这样子吧 前提是这些之和等于n
        //加一是为了有n

动态规划

代码如下:

class Solution {
         public   int integerBreak(int n) {
        //如果是动态规划的话 那只能是dp[n]=max(dp[n-1]*1,dp[n-2]*2)..这样子吧 前提是这些之和等于n
        //加一是为了有n
        int dp[]=new int[n+1];
        //dp[2]实际上是等于1的 但是用到他的时候其实是等于2的?
     if(n==2||n==3)
            return n-1;
        //再进行初始化
        dp[0]=0;
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=n;i++){
            //第一个循环是对应dp[i]这个最终结果
            int max=0;
            for(int j=1;j<i;j++){
                //第二个循环是对应那个
                if(max<dp[i-j]*j)
                    max=dp[i-j]*j;
            }
           //再把中间值给dp 应该是这样dp[i]能代表的是之前的值转换或者自己
            dp[i]=Math.max(max,i);
         /*   System.out.println(i);
            System.out.println(dp[i]);*/
        }
        return  dp[n];
    }
}

在这里插入图片描述


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进