C++에서 n을 0으로 줄이는 데 필요한 연산 수를 찾는 프로그램

<시간/>

숫자 n이 있다고 가정합니다. 이제 다음 중 하나를 수행할 수 있는 연산을 고려하십시오. 1. n을 1로 감소 2. n이 짝수이면 n / 2로 감소 3. n이 3으로 나누어 떨어지면 2로 감소 * (n / 3) 마지막으로 찾기 n을 0으로 줄이는 데 필요한 최소 연산 수.

따라서 입력이 n =16과 같으면 출력은 5가 됩니다. n =16인 경우에도 n/2만큼 4번 감소하면 1이 됩니다. 그런 다음 1을 줄여 0을 얻습니다. 따라서 총 5 작업.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

하나의 맵 dp 정의
dfs() 함수를 정의하면 x가 필요합니다.
렛 :=x
x가 dp에 있으면 -
- 반환 dp[x]
x <=0이면 -
- x를 반환
x가 1과 같으면 -
- 1 반환
md2 :=x 모드 2
md3 :=x 모드 3
ret :=최소 {ret, md2 + 1 + dfs((x - md2) / 2), md3 + 1 + dfs((x - md3) / 3)}
반환 dp[x] =ret
기본 메서드 호출에서 dfs(n)
반환

예

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
unordered_map <int, int> dp;
int dfs(int x){
   int ret = x;
   if(dp.count(x))
      return dp[x];
   if(x <= 0)
      return x;
   if(x == 1)
      return 1;
   int md2 = x % 2;
   int md3 = x % 3;
   ret = min({ret, md2 + 1 + dfs((x - md2) / 2), md3 + 1 + dfs((x - md3) / 3)});
   return dp[x] = ret;
}
int solve(int n) {
   return dfs(n);
}
int main(){
   int n = 16;
   cout << solve(n);
}