Ngắt số nguyên trong C ++

Giả sử chúng ta có một số nguyên dương n, chúng ta phải chia nó thành tổng của ít nhất hai số dương và lớn nhất là tích của các số nguyên đó. Chúng tôi phải tìm ra sản phẩm tối đa mà chúng tôi có thể nhận được. Vì vậy, nếu số là 10, thì câu trả lời sẽ là 36, vì 10 =3 + 3 + 4, 3 * 3 * 4 =36

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định phương thức giải quyết (), phương thức này sẽ lấy n, mảng dp và cờ
nếu n là 0, thì trả về 1
nếu dp [n] không phải là -1, thì trả về dp [n]
end:=n - 1 khi cờ được đặt, nếu không thì n
ret:=0
cho tôi trong phạm vi từ 1 đến hết
- ret:=max trong số ret và i * giải quyết (n - i, dp, false)
đặt dp [n]:=ret và trả về
Từ phương thức main, tạo một mảng dp có kích thước n + 1 và điền vào - 1
trả về giải quyết (n, dp)

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Ngắt số nguyên trong C ++

Ví dụ (C ++)

Đầu vào

Đầu ra