程序｜生活｜學到就是賺到
問題 題目在這。 解題思路 格子題，從左上到右下需要的最小步數。難點在給了個預算k，最多可以穿牆k次。找距離需要用BFS，不走回頭路就可以，比較簡單。但是這題在空間上是有可能走回頭路的，因為除了空間以外，還多了個狀態是已經穿牆幾次。放到queue裡面的應該是（坐標，穿牆次數）的tuple。所以關鍵在於不要把相同（坐標，穿牆次數）放queue里，不然會無法停止。 Python解法
問題總結 這題比較簡單，如果學過computer architecture，這個Reverse Polish Notation (RPN)基本就是個stack machine。很像彙編語言。用stack就可以解決。 坑 除法要求 that division between two integers should truncate toward zero. 測試數據裡面有負數, python裡面整數除法結果如果是小數，約成整數後是往小的方向約的。比如-0.4會變成-1，題目要求往0約，也就是-0.4變成0。用int(a/b)可解決。一個冷門知識。 Python解法
題目在這裡。 自己想的答案，bottom up dp不太好想，從top down + cache開始，寫了幾次，每次簡化一點，最終寫成這樣通過OJ。 Python 版本。 為了更好理解演算法，加了些log，記錄dfs被call了幾次和cache hit，和每個cache key被寫入次數（使用cache和不用cache的情況。 用coins = [1, 2, 5]和amount = 11為例子 用了cache 不用cache 運行完後cache的內容如下 正是從0到11每個amount的最少硬幣數。從此出發，想到bottom up dp正是需要構建如上cache的內容。dp[0] = 0，amount是0，當然一個硬幣不用。dp[amount]就看amount – coin值是不是正，而且之前是否有非-1的值。當算到amount的時候，前面dp[0]到d][amount-coin]都算過了。對所有的coin值都算一遍，把所有dp[amount – coin]的非-1最小值找出來，加1，就是dp[amount]。時間複雜度為O(amount * len(coins))。空間為 O(amount)。 過了多日以後自己重新想的Python寫法, 看看是否已經內化並掌握. 對比上面, 做了一些改進, dp list…
Read more
