算法-动态规划专题

前言 : 动态规划简述

动态规划在当前我们的理解下,其实就是一种变相的递归,我们查看一些资料也可以知道,动态规划其实属于递归的一个分支,通过把递归问题开辟的栈帧通过一定的手段放到某一种"表"中去

动态规划标准解题流
在我们«数据结构与算法分析»中是这样描述动规的
在前一节，我们看到可以被数学上递归表示的问题也可以表示成一种递归算法，在许多情形下对朴素的穷举搜索得到显著的性能改进。
任何数学递推公式都可以直接转换成递归算法，但是基本现实是编译器常常不能正确对待退归算法，结果导致低效的程序。当怀疑很可能是这种情况时，我们必须再给编译器提供一些
分解
帮助，将递归算法重新写成非递归算法，让后者把那些子问题的答案系统地记录在一个表内。利用这种方法的一种技巧叫作动 (dynamic programming)。
1 . 创建dp表(一维/二维数组)
2 . 确定我们的状态表示
---->方法是 经验+题目要求+分解为相同的子问题
---->目前已知的经验就是 以i位置为起点…/以i位置为末尾…
3 . 推导状态转移方程(相邻位置优先)
4 . 初始化(防止数组越界,处理边界位置)
5 . 填表,注意顺序(前 --> 后 / 后 --> 前)
6 . 返回值(这个跟你的开出来的dp表空间大小有关系)

7 . 空间优化(这个不是主要的…其实能写出来就不错了)

1 . 斐波那契模型

1.1 泰波那契数列

关于本题的具体分析见下

public class Fibonacci {
    /**
     * 寻找第 n 个泰波那契数
     *
     * @param n --> 第几个数
     * @return
     */
    public int tribonacci(int n) {
        创建dp表
        int[] dp = new int[n + 1];
        确定状态表示 --> 就是第几个泰波那契数
        确定状态转移方程 --> dp[n] = dp[n - 1] + dp[n - 2] + dp[n - 3]
        初始化
        if (n == 0 || n == 1) {
            return n;
        }
        if (n == 2) {
            return 1;
        }
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        填表(顺序从左到右)
        for (int i = 3; i < n + 1; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

关于这个比较简单的题,我们还有一点要说的,请注意,这个dp表的空间是不是开的有点浪费,其实不难看出,我们真正需要的是三个临时遍历在相互赋值迭代,其实这也就是我们的空间优化的思路…
通过滚动数组来实现空间优化

上图是我们的空间优化可视化…
代码实现如下

class Solution {
    public int tribonacci(int n) {
        if(n == 0 || n == 1){
            return n;
        }
        if(n == 2){
            return 1;
        }

        int a = 0;
        int b = 1;
        int c = 1;
        int d = 0;
        for(int i = 3; i <= n; ++i){
            d = a + b + c;
            a = b;
            b = c;
            c = d;
        }
        return d;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

1.2 最小花费爬楼梯

下面我们根据流程来分析一下这个题目
首先我们要明白的是那个位置是楼梯顶部…
这里的数组最后一个元素不是楼梯的顶端,最后一个元素的下一个才是

1. 创建dp表,这里我们的dp表开n+1个大小
2. 确定状态表示 —> dp[i] 表示到达i位置所需的最小花费
3. 确定状态转移方程(下图可视化)
   dp[i] = min(dp[i - 2] + cost[i - 2] , dp[i - 1] + cost[i - 1])
4. 初始化 0 和 1 位置
5. 填表,顺序从左到右
6. 返回值,返回dp[n]
   
   下面是我们的代码实现

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        //创建dp表
        int[] dp = new int[cost.length + 1];
        dp[0] = 0;
        dp[1] = 0;
        for(int i = 2; i < cost.length + 1; ++i){
            dp[i] = Math.min(dp[i - 1]+cost[i - 1],dp[i - 2]+cost[i - 2]);
        }
        return dp[cost.length];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

解法二其实就是从后向前遍历,题解如下

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        //解法2,我们换一种dp的思路(dp[i]为从i位置为起点到终点的最小花费)
        int len = cost.length;
        //初始化就应该换成最后两个元素,然后从后往前遍历
        int[] dp = new int[len];
        dp[len - 1] = cost[len - 1];
        dp[len - 2] = cost[len - 2];
        for(int i = len - 3; i >= 0; --i){
            dp[i] = Math.min(dp[i + 1],dp[i + 2]) + cost[i];
        }
        return Math.min(dp[0],dp[1]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

1.3 解码方法

本题分析如下
为什么能往动态规划上面想,其实我们每个解码都可以相互拆解,就有一种斐波那契的影子,所以很自然的向我们的动态规划上面去想

1. 创建dp表
2. 确定状态表示(dp[i]为解码到i位置的解码方法数目)
3. 推导状态转移方程(见下图)
   
4. 初始化 0 跟 1 位置
5. 填表,顺序从左到右
6. 输出返回值

class Solution {
    public int numDecodings(String s) {
        char[] chars = s.toCharArray();
        //创建dp表
        int[] dp = new int[s.length()];
        //确定状态表示 --> 就是解码到n位置的方法总数
        //确定状态转移方程(这个比较复杂)
        //初始化
        if (chars[0] != '0') {
            dp[0] = 1;
        }
        if (s.length() == 1) {
            return dp[0];
        }

        if (chars[1] >= '1' && chars[1] <= '9' && dp[0] != 0) {
            dp[1] += 1;
        }
        if ((chars[0] - '0') * 10 + chars[1] - '0' >= 10 && (chars[0] - '0') * 10 + chars[1] - '0' <= 26) {
            dp[1] += 1;
        }

        for (int i = 2; i < s.length(); ++i) {
            if (chars[i] >= '1' && chars[i] <= '9') {
                dp[i] += dp[i - 1];
            }
            if ((chars[i - 1] - '0') * 10 + chars[i] - '0' >= 10 && (chars[i - 1] - '0') * 10 + chars[i] - '0' <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[s.length() - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

本节会持续更新…