C++での整数ブレーク

正の整数nがあるとすると、それを少なくとも2つの正の数の合計に分割し、それらの整数の積を最大化する必要があります。入手できる最大の製品を見つける必要があります。したがって、数値が10の場合、答えは36になります。たとえば、10 =3 + 3 + 4、3 * 3 * 4 =36

これを解決するには、次の手順に従います-

• メソッドsolve（）を定義します。これには、n、配列dp、およびフラグが必要です

  。

• nが0の場合、1を返します

• dp [n]が-1でない場合は、dp [n]

  を返します。

• end：=n –フラグが設定されている場合は1、それ以外の場合はn

• ret：=0

• 範囲1から終了までのiの場合

  • ret：=retとi*の最大値solve（n – i、dp、false）

• set dp [n]：=ret and return

• mainメソッドから、サイズn + 1の配列dpを作成し、これに– 1

  を入力します。

• リターンsolve（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