C++：3つの可能な操作を与えられた動的プログラミング

Question

質問： 質問はこうです：私はN個の数字を持っています。 1. Xが2の倍数である場合、Xを2で割る。2. Xが3の倍数である場合、それを3で割る。3.減算X.から1 ...このコードは、動的プログラミングを使用して行われることを意図されているX = 0にする操作の最小数を探す

入力： 行1：Nライン2：N番号の配列X

出力： 行1：0にX1を低減するための操作の数...ラインN：操作の数は0

にXNを減らすためには、どのように私はこれをやって行くべきですか？

コード：

#include <bits/stdc++.h> 
using namespace std; 
int main(){ 
    int N; 
    cin >> N; 
    for (int i = 0; i < N; i++){ 
     int A, count = 0; 
     cin >> A; 
     while (A > 0){ 
      if (A%2 == 0){ 
       A /= 2; 
       count++; 
      } 
      else if (A%3 == 0){ 
       A /= 3; 
       count++; 
      } 
      else{ 
       A--; 
       count++; 
      } 
     } 
    cout << count << "\n"; 
    } 
} 

私は現在、心を持っているこのコードは（私は出力希望解決せず、コードは作業コードであることを意味する）いくつかのケースでは動作しません、Xiは=と言います10.私のコードは10/2、次に-1、次に/ 2、次に/ 2、-1となるので、5回の操作です。しかし、最適値は再び10 -1、/ 3、/ 3であり、-1であり、これは4回の演算である。どのように私はこの問題に私のソリューションをコードする必要があります誰もが考えている？ありがとう！どんな助けもありがとう！

Answer 1

あなたは、動的プログラミング言った：

std::vector<int> v{0}; 

for (int i = 1; i != N + 1; ++i) { 
    v.push_back(v.back() + 1); 
    if (i % 2 == 0) { 
     v.back() = std::min(v.back(), v[i/2] + 1); 
    } 
    if (i % 3 == 0) { 
     v.back() = std::min(v.back(), v[i/3] + 1); 
    } 
} 
return v.back();