Giả sử chúng ta có một số n. Bây giờ hãy xem xét một phép toán mà chúng ta có thể 1. Giảm n đi một 2. Nếu n là số chẵn thì giảm nó đi n / 2 3. Nếu n chia hết cho 3 thì giảm đi 2 * (n / 3) Cuối cùng tìm số hoạt động tối thiểu cần thiết để giảm n xuống 0.
Vì vậy, nếu đầu vào là n =16, thì đầu ra sẽ là 5, khi n =16 chẵn thì giảm n / 2 4 lần, nó sẽ là 1. Sau đó giảm nó đi 1 để được 0. Vậy tổng 5 hoạt động.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một bản đồ dp
-
Xác định một hàm dfs (), điều này sẽ lấy x,
-
ret:=x
-
nếu x nằm trong dp, thì -
-
trả về dp [x]
-
-
nếu x <=0, thì -
-
trả lại x
-
-
nếu x giống với 1 thì -
-
trả lại 1
-
-
md2:=x mod 2
-
md3:=x mod 3
-
ret:=tối thiểu là {ret, md2 + 1 + dfs ((x - md2) / 2), md3 + 1 + dfs ((x - md3) / 3)}
-
trả về dp [x] =ret
-
Từ lệnh gọi phương thức chính và trả về dfs (n)
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơ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);
} Đầu vào
16
Đầu ra
5