算法篇九 动态规划

动态规划难吗？说实话，我觉得很难，特别是对于 初学者来说，我当时入门动态规划的时候，是看 0-1 背包问题，当时真的是一脸懵逼。后来，我遇到动态规划的题， 看的懂答案，但就是自己不会做，不知道怎么下手。就像做递归的题，看的懂答案，但下不了手，关于递归的，我之前也写过一篇 套路的文章，如果对递归不大懂的，强烈建议看一看： 为什么你学不会递归，告别递归，谈谈我的经验 对于动态规划，春招秋招时好多题都会用到动态规划，一气之下，再 leetcode 连续刷了几十道题 之后，豁然开朗 ，感觉动态规划也不是很难，今天，我就来跟大家讲一讲，我是怎么做动态规划的题的，以及从中学到的一些 套路 。相信你看完一定有所收获 如果你对动态规划感兴趣，或者你看的懂动态规划，但却不知道怎么下手，那么我建议你好好看以下，这篇文章的写法，和之前那篇讲递归的写法，是差不多一样的，将会举大量的例子。如果一次性看不完，建议收藏，同时别忘了 素质三连 。 为了兼顾初学者，我会从最简单的题讲起，后面会越来越难，最后面还会讲解，该如何优化。因为 80% 的动规都是可以进行优化的。不过我得说，如果你连动态规划是什么都没听过，可能这篇文章你也会压力山大。 动态规划，无非就是利用 历史记录，来避免我们的重复计算。而这些 历史记录，我们得需要一些 变量来保存，一般是用 一维数组或者 二维数组 来保存。下面我们先来讲下做动态规划题很重要的三个步骤， 如果你听不懂，也没关系，下面会有很多例题讲解，估计你就懂了。之所以不配合例题来讲这些步骤，也是为了怕你们脑袋乱了 第一步骤：定义 数组元素的含义 ，上面说了，我们会用一个数组，来保存历史数组，假设用一维数组 dp[] 吧。这个时候有一个非常非常重要的点，就是规定你这个数组元素的含义，例如你的 dp[i] 是代表什么意思？ 第二步骤：找出 数组元素之间的关系式，我觉得动态规划，还是有一点类似于我们高中学习时的 归纳法的，当我们要计算 dp[n] 时，是可以利用 dp[n-1]，dp[n-2]...dp[1]，来推出 dp[n] 的，也就是可以利用 历史数据 来推出新的元素值，所以我们要找出数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，这个就是他们的关系式了。而这一步，也是最难的一步，后面我会讲几种类型的题来说。