Chia số nguyên để tối đa hóa tích trong JavaScript

Mô tả vấn đề

Chúng ta cần viết một hàm JavaScript nhận vào số nguyên num làm đối số duy nhất.

Hàm phải chia số nguyên này thành ít nhất hai phần sao cho tổng các phần bằng num và tích của chúng là lớn nhất có thể. Hàm trả về tích lớn nhất này.

Ví dụ, nếu đầu vào là:

const num = 10;

Thì đầu ra nên là:

const output = 36;

Giải thích đầu ra

Vì 10 có thể chia thành 3 + 3 + 4, tích = 36.

Ví dụ minh họa

Mã thực hiện (quy hoạch động):

const num = 10; 
const breakInt = (num = 2) => { 
  const dp = new Array(num + 1).fill(0); 
  dp[0] = 0; 
  dp[1] = 1; 
  for(let i = 2; i <= num; i++){ 
    for(let j = 1; 2*j <= i; j++){ 
      dp[i] = Math.max(dp[i], Math.max(j, dp[j]) * Math.max(i-j, dp[i-j]) ); 
    }; 
  }; 
  return dp[num]; 
}; 
console.log(breakInt(num));

Đầu ra

Kết quả trong console sẽ là:

36