leetcode-python动态规划题入门

关于动态规划，提到这个词，可能很多刷过题的测试都会感到头疼，这个难度真的是高出其他题型至少半个次元，我也不例外，要不是其他题型基本都刷光了，也不会来啃动态的题。

周六，一个简单的早上我简单的做了一道简单难度的动态规划题，这给大家简单说说，诸如上台阶的多种方法，股票买入的最佳机会，黑瞎子掰苞米的最佳收手时间，打家劫舍的 经典题型，这次的题也差不多。

相信题意很简单，栅栏的柱子数 和 涂料数 都给你，让你求出一共多少种图的方法，其中有个条件，就是同一种颜色的柱子最多只能2个。也就是说 你可以：黄黄红，但是不可以黄黄黄。

针对这道题，我们可能一开始没啥思路，这里教一个小技巧，先把影响咱思维的条件删掉，看看有啥思路。也就是说，我们去掉同一种颜色柱子最多只能2根的这个设定。来考虑，那么就简单了。排列组合嘛。

假设5个柱子，3个颜色。那么每个柱子都可以涂3种情况，一共5根。

那最终结果所有情况就是：3*3*3*3*3 = 3的5次方。很简单就有了主体思路，然后再加上限制条件，就是不能涂超过2根一样颜色的设定。

假设只有1根 ，那么简单了。就是 3种颜色 3种结果

假设只有2根，那么因为不触碰到设定最多2根所以也简单。就是3*3种结果

假设有3根，这个时候才开始要考虑。前俩根的所有情况一共是 3*3 种，那么第三根呢？它有几种可以涂的情况呢？它可以这么考虑，要么只要不和第二根颜色相同，要么不和第一根颜色相同，这俩种情况都铁定不会触犯限制。不管你颜色一不一样，反正第三根满足不和第一根 或 第二根相同就好。

现在让我们来看下一共的可能情况：

三根柱子：A B C

三种颜色：红 黄 蓝

A B C

红 红 (黄/蓝)

红 黄 (红/黄/蓝)

红 蓝 (红/黄/蓝)

黄 红 (红/黄/蓝)

黄 黄 (红/蓝)

黄 蓝 (红/黄/蓝)

蓝 红 (红/黄/蓝)

蓝 黄 (红/黄/蓝)

蓝 蓝 (红/黄)

所以结果很明显了。我们要么可以用加法观念，要么用减法观念：

3根柱子的最终结果=

加法规律：

只有1根时的总结果数 * (颜色数-1)+只有2根时的总结果数*(颜色数-1)

减法规律：

3根无视规则的总结果数 - 颜色数 (不符合动态规划题意,抛弃)

给大家看一下加法观念的 代码：

这里 对 n 柱子数=0 / 1 /2 的时候 直接写死了返回值。

把最终所有的情况放进了 列表dp中（为啥叫dp？别问，大佬们都这么写）

最后返回dp最后一个元素就是最终结果了。

关于动态规划的窍门：

动态规划必然有一个列表存放 最终不同阶梯的最终结果。记住，每个结果，都是由前面最贴近的n个结果 演化出来的。也就是说你想知道 10个柱子有多少结果，你就必须知道8个柱子的结果 和9个柱子的结果。你想知道 8个柱子的结果，你就必须知道 6个柱子和7个柱子的结果。依次往前逆推，推到第一二个结果为止，这最开始的结果，你一定是闭眼睛都能知道的答案，这就是动态规划的主体思维。具体往前要推算多少种，那要看题，本题中说不能三根柱子一个颜色，那么就是需要考虑前面2个柱子。如果说不能五个一个颜色，那么你就要考虑前面4个柱子了。

如果能理解我上述所说的技巧。那么恭喜你，那些个bat等一线大厂的测试开发面试算法题，难度最复杂的题目中之一的动态规划，你可以无忧了。

所谓算法，其实考的不是你的代码水平，而是脑筋急转弯，看你灵活不灵活，对于我们普通人来说，天下算法就这么几十种题型，每种的核心解决思路我全背下来，不怕去不了bat大厂当测开。

喜欢的点个赞分享一下吧？