给定一个数字n，每次可以选择一项。
令n = n - 1
令n = n / 2 , if n % 2 == 0
令n = n / 3 , if n % 3 == 0
求最少需要多少步可以让其变成1.
减1操作可以看作是为了除法做准备，连续超过两次减1再除2是不优的，连续超过三次减1再除2也是不优的。
可以根据下一步除2还是除3来分出两个分支。
用搜索表示就是
\[
dfs(n) = min(dfs(n / 2) + n \% 2 , dfs(n / 3) + n \% 3) + 1
\]
对于n来说，其可以搜索到的数字是 \(\lfloor\frac{n}{2^a3^b} \rfloor\) , 根据a，b的取值不同可以有\(log^2(n)\)个状态。
即使用记忆化之后，单次查询复杂度是\(log^2(n)\)
#include<unordered_map>
#include<iostream>
using namespace std;
unordered_map<long long , int> Dp;
int Dfs(long long n)
{
if(n <= 1) return 0;
if(Dp.count(n)) return Dp[n];
return Dp[n] = min(Dfs(n / 2) + n % 2 + 1 , Dfs(n / 3) + n % 3 + 1);
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T;
long long n;
cin >> T;
while(T--)
{
cin >> n , cout << Dfs(n) << '\n';
}
return 0;
}