343.整数拆分

链接：343.整数拆分
难度：Medium
标签：数学、动态规划
简介：给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

题解 1 - typescript

• 编辑时间：2020-07-30
• 执行用时：84ms
• 内存消耗：37.4MB
• 编程语言：typescript
• 解法介绍：dp[i]=i 的最大值。

function integerBreak(n: number): number {
  const dp = new Array(n + 1).fill(0);
  for (let i = 2; i <= n; i++) {
    let max = 0;
    for (let j = 1; j <= i - 1; j++) {
      max = Math.max(max, j * Math.max(i - j, dp[i - j]));
    }
    dp[i] = max;
  }
  return dp[n];
}