如何解决动态规划问题
date
Jul 29, 2019
slug
solve-dp-problems
status
Published
tags
Dev
summary
解决动态规划的好办法
type
Post
曾经的我以为动态规划很神秘，很难理解。后来随着刷的动态规划相关的题越来越多，对于动态规划也就驾轻就熟了。我一开始来认识动态规划是通过概念来理解的，这对于我来说总是显得晦涩。我不是一个善于死记理论的人，反而是通过多刷题，回头再去看动态规划的使用情况则是有一种恍然大悟感。这样的获得想必也不会轻易忘记。刷题并不能让人变得聪明，但确实能够锻炼一个人的思维。
img
递归 + 数组 = 动态规划
先看一眼概念也未必是坏事：动态规划 - 维基百科，自由的百科全书
动态规划的所有题目，在不考虑性能的情况下，都可以使用简单的递归来解决。
题目
下面来看一道 LeetCode 经典动态规划题目：(70) Climbing Stairs - LeetCode
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Note: Given n will be a positive integer.
Example 1:
Example 2:
递归
公式如下（这个也是做动态规划必须要列出的公式）
$$
f(n)=\begin{cases}
n,\quad n\leq 2 \\\\
f(n-1)+f(n-2),\quad x>2
\end{cases}
$$
我们来试试用简单的递归来解决这个问题：
如果我们这时候计算的是
climbStairs(5)，通过下图可以看到我们一共计算 f(3) 2次、 f(2) 3次、 f(1) 2次。这是在台阶数 n 很小的情况下，如果 n 很大的话，重复计算的模块会变的更多。
DP
数组记录中间结果
这个时候如果我们能够通过一个数组来记录中间结果就好了，当上图中的每一个节点如果已经计算过，就不再重复计算了。
DP2
代码如下：
去掉递归
递归会新建很多局部变量，建立很多栈帧，带来很多不必要的消耗，如果能够去除递归效率会有进一步的提升。
$$
f(n)=\begin{cases}
n,\quad n\leq 2 \\\\
f(n-1)+f(n-2),\quad x>2
\end{cases}
$$
上面我们都是从图中的根结点一步一步向下计算，是一个深度优先搜索的过程，如果我们从根节点向上算就能去掉递归了。
DP-3
代码如下：
动态规划题目
多刷点题，就啥都明白了。