ダイナミックプログラミングNでc++を表す

問題は,Nとnumberが与えられた場合,Nと4則演算のみで表す方法で,Nの使用回数の最大値を求める問題である.
e.g.N=5, number=1212=5+5+(5/5)+(5/5)->6個12=55/5+5/5->5個12=(55+5)/5->4個
最大値が4であるため、4を返します.
ここで逆に考えるとNは1個2個3個….仕事でできる数の集合を考えてみましょう.これらのセットに検索する番号がある場合は、作成できる番号を返します.
5が1の場合={5}2個5時={55, 5+5, 5-5, 5*5, 5/5}3個5時={555, 5+55, 55+5, 5+5+5, 5-55, 55-5, 5-5-5, 5*55, 55*5, 5*5*5, 5/55, 55/5 , 5/5/5} ここから,2つの場合に用いられる演算は,3つの場合に用いられる演算に用いられることが分かる.例えば、5が3の場合、{5+5+5}は5が1の場合、{5}と5が2の場合、{5+5}演算が加算される.

1.Memoization方式が考えられ、それをdpと表す

vector<unordered_set<int>> dp(8);(2 Dベクトルを宣言するのではなくunordered_setを使用するのは、格納された値がソートされる必要がなく、重複する値が複数回書き込まれる必要がないためです)
e.g.N=5, number=12(ただし&はすべての4則演算を表す)
dp[0]=5が1の場合{5}--N0dp[1]=5が2の場合{55, N0 & N0}--N1dp[2]=5が3の場合{555, N0 & N1, N1 & N0}--N2dp[k]=5がkの場合{555... (k개 만큼), Ni & Nj (i+j+1=k 인 집합)}

2.k個Nの関数を作成する

5、55、555などの数値の関数を作成します.

#include <cmath>

int makeNumber (int N, int idx) {
    int answer=0;
    while (idx>0) {
        idx--;
        answer+=N*pow(10, idx);
    }
    return answer;
}

3.dp[k]に値を保存する

(1)dp[0]は、1つのNを使用して数値を作成するので、1
(2)最初のすべての場合、デフォルト値は5, 55, 555, 5555であるため、2番目に作成されたk개의 N을 만드는 함수が呼び出されて保存される
(3)i+j+1=kの場合、1つの数字を抽出してから、4つの演算値をdp[k]に保存する(マイナス記号と除算に注意)
(4)dp[k].count(number)>0,すなわちk+1個Nで作成可能な集合中の要素数の個数が0より大きい,すなわちk+1을 return

  for (int k=1; k<MAX; k++) {
      dp[k].insert(makeNumber(N, k+1));
 
      for (int i=0; i<MAX; i++) {
          for (int j=0; j<MAX; j++) {
              if (i+j+1!=k) continue;
         
              for (int op1: dp[i]) {
                  for (int op2: dp[j]) {
                      dp[k].insert(op1+op2);
                      if (op1-op2>0) dp[k].insert(op1-op2);
                      dp[k].insert(op1*op2);
                      if (op1/op2>0) dp[k].insert(op1/op2);
                  }
              }
          }
      }
        if (dp[k].count(number)>0) 
            return k+1;
  }

完全なコード

#include <string>
#include <vector>
#include <unordered_set>
#include <cmath>

const int MAX=8;

using namespace std;

int makeNumber (int N, int idx) {
  int answer=0;
  while (idx>0) {
      idx--;
      answer+=N*pow(10, idx);
  }
  return answer;
}

int solution(int N, int number) {
  if (N==number) return 1; // 이 경우의 수도 꼭 포함해주어야 함
  vector<unordered_set<int>> dp(MAX);
 
  dp[0].insert(N);
 
  for (int k=1; k<MAX; k++) {
      dp[k].insert(makeNumber(N, k+1));
     
      for (int i=0; i<MAX; i++) {
          for (int j=0; j<MAX; j++) {
              if (i+j+1!=k) continue;
             
              for (int op1: dp[i]) {
                  for (int op2: dp[j]) {
                      dp[k].insert(op1+op2);
                      if (op1-op2>0) dp[k].insert(op1-op2);
                      dp[k].insert(op1*op2);
                      if (op1/op2>0) dp[k].insert(op1/op2);
                  }
              }
          }
      }
        if (dp[k].count(number)>0) 
            return k+1;
  }
  return -1;    
}