做了一道很有意思的题目,要求是从左上角开始,在HP不掉到0的情况下,到达右下角。虽然明显是使用动态规划来解,但是其中隐藏了一些技巧 。这里,如果从左上角开始进行DP将使得问题复杂化,技巧就是反向,从终点开始反向DP,这篇博客将详细这种方法的应用条件。
dynamicprograming
LeetCode_091: DecodeWays 从DFS到动态规划
从LeetCode中有一些数字字符串处理问题,它们的解法有许多相似之处,但是在具体操作上又有所不同,91题和93题IPAddress就是比较好的范例。这篇博客主要从DFS和DP两种方法来分析问题,并判断适应问题环境使用合适的方法。
LeetCode_131: Palindrome Partition 回文字符串
回文字符串问题可以看做是一个划分链问题,这个和算法导论中介绍动态规划时的矩阵链乘法是一样的,找到一个最优的划分方案。很自然的想到动态规划来得到一个回文串的真值表,然后就是要列举出所有的情况,回溯法可以做到,自然而然的DP+BackTracking解决掉。
LeetCode_010: 正则表达式匹配 与 044: 通配符匹配
最近在攻略动态规划,在做正则表达式匹配的时候看错了题目,发现写出来的是通配符匹配,后来看了下什么是正则表达式才明白过来。这两道题都是有很多解法的题目,按照标签刷题目还是限制了自己的思路,一开始就没有往其它地方想。事实上,通配符匹配用贪心算法(可以看做一种特殊的动态规划)更合适。
LeetCode_085: Maximal Rectangle 动态规划
这道题很难想,主要有两种解法,一种是把这道题目转化成之前那道(#084)直方图面积计算的题目,使用栈来做,但是还有更优雅的方法,使用DP。这两种方法的时间复杂度都是O(mn),空间复杂度都是O(n)。
LeetCode_313: Super Ugly Number
这道题一种普遍的解法是动态规划。但是同样是动态规划,也有优劣之分。这篇博客贡献一份36ms(80%+)的答案,推荐这份答案不仅是因为速度,还是因为这种思路十分清晰,当然也可以参考讨论区中的7行的动态规划答案,也是十分优秀的。