LeetCode_174: Dungeon Game 动态规划

做了一道很有意思的题目,要求是从左上角开始,在HP不掉到0的情况下,到达右下角。虽然明显是使用动态规划来解,但是其中隐藏了一些技巧 。这里,如果从左上角开始进行DP将使得问题复杂化,技巧就是反向,从终点开始反向DP,这篇博客将详细这种方法的应用条件。

阅读更多

LeetCode_131: Palindrome Partition 回文字符串

回文字符串问题可以看做是一个划分链问题,这个和算法导论中介绍动态规划时的矩阵链乘法是一样的,找到一个最优的划分方案。很自然的想到动态规划来得到一个回文串的真值表,然后就是要列举出所有的情况,回溯法可以做到,自然而然的DP+BackTracking解决掉。

阅读更多

LeetCode_010: 正则表达式匹配 与 044: 通配符匹配

最近在攻略动态规划,在做正则表达式匹配的时候看错了题目,发现写出来的是通配符匹配,后来看了下什么是正则表达式才明白过来。这两道题都是有很多解法的题目,按照标签刷题目还是限制了自己的思路,一开始就没有往其它地方想。事实上,通配符匹配用贪心算法(可以看做一种特殊的动态规划)更合适。

阅读更多