ตัวแบ่งจำนวนเต็มใน C++

สมมติว่าเรามีจำนวนเต็มบวก n เราต้องแยกมันเป็นผลรวมของจำนวนบวกอย่างน้อยสองจำนวนและเพิ่มผลคูณของจำนวนเต็มเหล่านั้นให้มากที่สุด เราต้องหาสินค้าให้ได้มากที่สุด ดังนั้นหากตัวเลขคือ 10 คำตอบจะเป็น 36 เช่น 10 =3 + 3 + 4, 3 * 3 * 4 =36

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดวิธีการแก้ปัญหา () ซึ่งจะใช้เวลา n อาร์เรย์ dp และแฟล็ก

• ถ้า n เป็น 0 ให้คืนค่า 1

• ถ้า dp[n] ไม่ใช่ -1 ให้คืนค่า dp[n]

• end :=n – 1 เมื่อตั้งค่าแฟล็ก มิฉะนั้น n

• ยกเลิก :=0

• สำหรับผมอยู่ในช่วง 1 ถึงสิ้นสุด

  • ret :=สูงสุดของ ret และ i* แก้ (n – i, dp, false)

• set dp[n] :=ret และ return

• จากวิธีหลัก ให้สร้างอาร์เรย์ dp ขนาด n + 1 แล้วเติมด้วย – 1

• กลับแก้(n, dp)

ตัวอย่าง (C++)

ให้เราดูการใช้งานต่อไปนี้เพื่อทำความเข้าใจ −

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(int n, vector <int>& dp, bool flag = true){
      if(n == 0) return 1;
      if(dp[n] != -1) return dp[n];
      int end = flag? n - 1: n;
      int ret = 0;
      for(int i = 1; i <= end; i++){
         ret = max(ret, i * solve(n - i, dp, false));
      }
      return dp[n] = ret;
   }
   int integerBreak(int n) {
      vector <int>dp(n + 1, -1);
      return solve(n, dp);
   }
};
main(){
   Solution ob;
   cout << (ob.integerBreak(10));
}

อินพุต

10

ผลลัพธ์

36