1002.Shortest path

簽到題 記憶化搜索

題目大意

給定一個正整數 $n$ ，可以對其進行以下操作：

1. 如果 $n$ 能被 $3$ 整除，則可以使 $n=n/3$ ;
2. 如果 $n$ 能被 $2$ 整除，則可以使 $n=n/2$ ;
3. 使 $n=n?1$

求使得 $n$ 變成 $1$ 的最少操作次數

解題思路

將樣例Output輸出即可

這題不難，但確實精彩()//畢竟……
《釘耙編程”中國大學生算法設計超級聯賽》是由hdu自主研發的一款全新開放世界冒險競賽。競賽發生在一個被稱作“hdu”的幻想世界，在這里，被編譯器選中的人將被授予“C++”，導引代碼之力。你將扮演一位名為“acmer”的神秘角色，在自由的打題中邂逅性格各異能力獨特的STL容器，和他們一起擊敗強題，找回AC的代碼

不鬧了，解題吧()

不難看出操作 $3$ 的收益最低，是不滿足操作 $1,2$ 的時候湊條件用的。
而由于只允許整除，操作 $1,2$ 的優劣性不好評估（因為要夾雜操作 $3$ 而不單純是減少的量的區別），因此每次對本次進行的兩種操作方案進行比較。

按以下操作遞歸處理 $n$ ：

1. 如果 $n=1$ ，則返回 $0$ ；
2. 進行若干次（可能0次）操作 $3$ 使得 $n$ 能被 $2$ 整除，執行操作 $2$
3. 進行若干次（可能0次）操作 $3$ 使得 $n$ 能被 $3$ 整除，執行操作 $1$

由于數據范圍的關系，傳統的DFS會超時，因此需要使用記憶化搜索
即每次計算完某個數（記為 $x$ ）的結果，將其保存下來，后續搜索 $x$ 時就無需繼續搜索到底部，直接輸出這個數的結果即可
記憶化搜索可以用 map 實現，頻繁讀取而不考慮元素順序的可以使用 unordered_map ，有效降低時間空間復雜度

下面兩份使用了 map ，代碼完全一致；上面一份僅僅將 map 改為了 unordered_map

時間復雜度

$O(t{\log }^{2}n)$

參考代碼

參考代碼為已AC代碼主干，其中部分功能需讀者自行實現

unordered_map<ll,ll> mp;
ll dfs(ll n){if(n<=1) return 1-n;if(mp[n]) return mp[n];ll t1,t2;t1=n%2+1+dfs(n/2);t2=n%3+1+dfs(n/3);return mp[n]=min(t1,t2);
}
void solve()
{ll n;cin >> n;cout << dfs(n) << endl;
}