leetcode343. 整数拆分
整数 拆分
2023-09-27 14:25:54 时间
给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
思路:动态规划,等于之前j的某个最优解或者j本身,乘i-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] = Math.max(dp[i], Math.max(j,dp[j]) * (i - j));
return dp[n];
}
}
相关文章
- 用递归法将一个整数n转换成字符串。
- C#,实用新型加强版的整数数组
- 关于postgresql:将字符串转换为整数-Postgres
- 【面试题】Java 2个(多个)大整数相加如何实现
- 【Redis】三、Redis整数集合和压缩列表
- c语言提取浮点型数据的整数部分与小数部分几种方法
- 【C语言】从字符串中提取正整数和负整数
- 力扣解法汇总12-整数转罗马数字
- 149、【动态规划】leetcode ——343. 整数拆分(C++版本)
- java之整数的分解可以理解为倒序输出
- 算法训练 出现次数最多的整数
- LeetCode 7. 整数反转
- lqb 基础练习 查找整数 (遍历)
- [LeetCode] 13. Roman to Integer 罗马数字转化成整数
- 习题4.8 计算并输出一个整数各位数字之和。如,5423的各位数字之和为5+4+2+3。
- Java //PP2.10 编写一个程序,确定瓶子里的硬币总面值并以美元和美分为单位打印输出总钱数。读取分别代表25美分、10美分、5美分、1美分硬币数量的整数
- Python random() 函数,产生整数随机数,浮点数随机数
- [Mysql] 整数与浮点数精度处理函数