曾经的我以为动态规划很神秘，很难理解。后来随着刷的动态规划相关的题越来越多，对于动态规划也就驾轻就熟了。我一开始来认识动态规划是通过概念来理解的，这对于我来说总是显得晦涩。我不是一个善于死记理论的人，反而是通过多刷题，回头再去看动态规划的使用情况则是有一种恍然大悟感。这样的获得想必也不会轻易忘记。刷题并不能让人变得聪明，但确实能够锻炼一个人的思维。
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:
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:
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
递归
公式如下（这个也是做动态规划必须要列出的公式）
我们来试试用简单的递归来解决这个问题：
/**
* 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
代码如下：
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;
}
}
去掉递归
递归会新建很多局部变量，建立很多栈帧，带来很多不必要的消耗，如果能够去除递归效率会有进一步的提升。
上面我们都是从图中的根结点一步一步向下计算，是一个深度优先搜索的过程，如果我们从根节点向上算就能去掉递归了。
DP-3
代码如下：
/**
* 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];
}
}
动态规划题目
多刷点题，就啥都明白了。
网友评论