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"; 
    } 
} 

나는 현재 어떤 경우에는 작동하지 않습니다 염두에두고 (I 출력하지 원하는 솔루션을 의미하고, 코드가 작동하는 코드가 있음)이 코드 사이를 말할 = 10. 내 코드는 10/2, -1, 2/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();