程序｜生活｜学到就是赚到
问题 题目在这。 解题思路 格子题，从左上到右下需要的最小步数。难点在给了个预算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
