如何解决动态规划问题

曾经的我以为动态规划很神秘,很难理解。后来随着刷的动态规划相关的题越来越多,对于动态规划也就驾轻就熟了。我一开始来认识动态规划是通过概念来理解的,这对于我来说总是显得晦涩。我不是一个善于死记理论的人,反而是通过多刷题,回头再去看动态规划的使用情况则是有一种恍然大悟感。这样的获得想必也不会轻易忘记。刷题并不能让人变得聪明,但确实能够锻炼一个人的思维。

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:

1
2
3
4
5
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

1
2
3
4
5
6
Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

递归

公式如下(这个也是做动态规划必须要列出的公式)
$$
f(n)=\begin{cases}
n,\quad n\leq 2 \\
f(n-1)+f(n-2),\quad x>2
\end{cases}
$$
我们来试试用简单的递归来解决这个问题:

1
2
3
4
5
6
7
8
9
10
11
/**
* Created by jacob on 2019-08-20.
*/
public class Solution {
public int climbStairs(int n) {
if (n <= 2) { // 递归终结点
return n;
}
return climbStairs(n - 1) + climbStairs(n - 2);
}
}

如果我们这时候计算的是 climbStairs(5),通过下图可以看到我们一共计算 f(3) 2次、 f(2) 3次、 f(1) 2次。这是在台阶数 n 很小的情况下,如果 n 很大的话,重复计算的模块会变的更多。

DP

数组记录中间结果

这个时候如果我们能够通过一个数组来记录中间结果就好了,当上图中的每一个节点如果已经计算过,就不再重复计算了。

DP2

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int climbStairs(int n) {
int[] dp = new int[n + 1];
return this.climbStairs(dp, n);
}

private int climbStairs(int[] dp, int n) {
if (n <= 1) {
return 1;
}
if (dp[n] > 0) {
return dp[n];
}
int num = climbStairs(dp, n - 1) + climbStairs(dp, n - 2);
dp[n] = num;
return num;
}
}

去掉递归

递归会新建很多局部变量,建立很多栈帧,带来很多不必要的消耗,如果能够去除递归效率会有进一步的提升。
$$
f(n)=\begin{cases}
n,\quad n\leq 2 \\
f(n-1)+f(n-2),\quad x>2
\end{cases}
$$
上面我们都是从图中的根结点一步一步向下计算,是一个深度优先搜索的过程,如果我们从根节点向上算就能去掉递归了。

DP-3

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* Created by jacob on 2019-08-20.
*/
public class Solution2 {
public int climbStairs(int n) {
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
if (i <= 2) {
dp[i] = i;
} else {
dp[i] = dp[i - 1] + dp[i - 2];
}
}
return dp[n];
}
}

动态规划题目

多刷点题,就啥都明白了。