春节7天练 | Day 7：贪心、分治、回溯和动态规划

<p><img src="https://static001.geekbang.org/resource/image/c9/8d/c9683a523cd6ef4e8f574c26e9e5fc8d.jpg" alt="" /></p> <p>你好，我是王争。今天是节后的第一个工作日，也是我们“春节七天练”的最后一篇。</p> <hr /> <h2>几种算法思想必知必会的代码实现</h2> <h3>回溯</h3> <ul> <li> <p>利用回溯算法求解八皇后问题</p> </li> <li>利用回溯算法求解 0-1 背包问题</li> </ul> <h3>分治</h3> <ul> <li>利用分治算法求一组数据的逆序对个数</li> </ul> <h3>动态规划</h3> <ul> <li> <p>0-1 背包问题</p> </li> <li> <p>最小路径和（详细可看 @Smallfly 整理的 Minimum Path Sum）</p> </li> <li> <p>编程实现莱文斯坦最短编辑距离</p> </li> <li> <p>编程实现查找两个字符串的最长公共子序列</p> </li> <li>编程实现一个数据序列的最长递增子序列</li> </ul> <h2>对应的 LeetCode 练习题（@Smallfly 整理）</h2> <ul> <li>Regular Expression Matching（正则表达式匹配）</li> </ul> <p>英文版：<a href="https://leetcode.com/problems/regular-expression-matching/"><a href="https://leetcode.com/problems/regular-expression-matching/">https://leetcode.com/problems/regular-expression-matching/</a></a></p> <p>中文版：<a href="https://leetcode-cn.com/problems/regular-expression-matching/"><a href="https://leetcode-cn.com/problems/regular-expression-matching/">https://leetcode-cn.com/problems/regular-expression-matching/</a></a></p> <ul> <li>Minimum Path Sum（最小路径和）</li> </ul> <p>英文版：<a href="https://leetcode.com/problems/minimum-path-sum/"><a href="https://leetcode.com/problems/minimum-path-sum/">https://leetcode.com/problems/minimum-path-sum/</a></a></p> <p>中文版：<a href="https://leetcode-cn.com/problems/minimum-path-sum/"><a href="https://leetcode-cn.com/problems/minimum-path-sum/">https://leetcode-cn.com/problems/minimum-path-sum/</a></a></p> <!-- [[[read_end]]] --> <ul> <li>Coin Change （零钱兑换）</li> </ul> <p>英文版：<a href="https://leetcode.com/problems/coin-change/"><a href="https://leetcode.com/problems/coin-change/">https://leetcode.com/problems/coin-change/</a></a></p> <p>中文版：<a href="https://leetcode-cn.com/problems/coin-change/"><a href="https://leetcode-cn.com/problems/coin-change/">https://leetcode-cn.com/problems/coin-change/</a></a></p> <ul> <li>Best Time to Buy and Sell Stock（买卖股票的最佳时机）</li> </ul> <p>英文版：<a href="https://leetcode.com/problems/best-time-to-buy-and-sell-stock/"><a href="https://leetcode.com/problems/best-time-to-buy-and-sell-stock/">https://leetcode.com/problems/best-time-to-buy-and-sell-stock/</a></a></p> <p>中文版：<a href="https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/"><a href="https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/">https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/</a></a></p> <ul> <li>Maximum Product Subarray（乘积最大子序列）</li> </ul> <p>英文版：<a href="https://leetcode.com/problems/maximum-product-subarray/"><a href="https://leetcode.com/problems/maximum-product-subarray/">https://leetcode.com/problems/maximum-product-subarray/</a></a></p> <p>中文版：<a href="https://leetcode-cn.com/problems/maximum-product-subarray/"><a href="https://leetcode-cn.com/problems/maximum-product-subarray/">https://leetcode-cn.com/problems/maximum-product-subarray/</a></a></p> <ul> <li>Triangle（三角形最小路径和）</li> </ul> <p>英文版：<a href="https://leetcode.com/problems/triangle/"><a href="https://leetcode.com/problems/triangle/">https://leetcode.com/problems/triangle/</a></a></p> <p>中文版：<a href="https://leetcode-cn.com/problems/triangle/"><a href="https://leetcode-cn.com/problems/triangle/">https://leetcode-cn.com/problems/triangle/</a></a></p> <hr /> <p>到此为止，七天的练习就结束了。这些题目都是我精选出来的，是基础数据结构和算法中最核心的内容。建议你一定要全部手写练习。如果一遍搞不定，你可以结合前面的章节，多看几遍，反复练习，直到能够全部搞定为止。</p> <p>学习数据结构和算法，最好的方法就是练习和实践。我相信这在任何知识的学习过程中都适用。</p> <p>最后，祝你工作顺利！学业进步！</p>