动态规划

动态规划题的特点

最明显的特点：求最优解
动态规划题一般只需要求步数之类的，不需要求具体方案（如果需要具体方案还是要用BFS或者递归来做）

动态规划一般都可分解为子问题
动态规划需要无后效性，即后面的结果可以利用前面的结果，但是不会改变前面的结果

动态规划一般步骤

1.确定状态

主要是思考最后一步，然后将最后一步去掉就转换成立规模更小的的n-1步的子问题

状态也可认为是某个情况下的最优。例如背包问题：dp[i][j]可认为是有 i 件物品 背包容量还剩 j 时的最优。

2.确定转移方程

就是将第$n$步与$n-1$步等前面的几步建立联系，得一个推导公式，也就是转移公式，确定需要的储存数组

存储数组就是用来存储前面的状态。

3.考虑初始条件和边界情况

一般的初始条件都是$f[0] = 0$或$f[0][0] = 0$,具体分析
边界情况主要就是考虑数组是否会越界，什么时候停止循环，将不可能的状态设置成了无穷大，要避免计算超过范围也需要避免

4.明白计算顺序

一般的计算顺序就是从左到右计算即从1开始来计算到n，因为第n步需要第1步的状态

例题

主页还有很多例题，这里是最典型的几种题目，看不懂也没关系，多看，多练，自然而然就会了。主要是要理解上面的特点和一般步骤，知道如何确定状态和状态转移方程。

爬楼梯问题

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

1
2
3
4
5
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：

1
2
3
4
5
6
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

数据范围：1 <= n <= 45

思路

很容易想到状态就是到达第 i 个楼梯的走法数量

这个时候到达第 i 个楼梯有几种可能？

—— 两种，从上一级台阶，走一步；从上上级台阶走两步

那么走到当前台阶有多少种走法？dp[i] = dp[i-1] + dp[i-2]

状态和状态转移方程都有了，写代码

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostrem>

using namespace std;

const int N = 50;
int n, dp[N];

int main() {
    cin >> n;
    dp[0] = 0, dp[1] = 1;
    for (int i = 2; i <= n; ++i) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    cout << dp[n] << endl;
}

硬币问题

给定一个数组，表示硬币的面值，比如数组A = {2,5,7}，表示有2元面值的硬币，5元面值的硬币，7元面值的硬币；然后给定一个价格例如27。要求计算用最少数量的硬币得到面值之和为27的组合，只需要得到硬币个数。

问题分析

问题要求求最少硬币的个数，但是没有要求求具体是那几个硬币，而且看到最少，一般就可以用动态规划来解题

  1. 确定状态
    这道题的状态就是面值为$M-A[j]$的结果，也就是最后一步呀让n-1步加上一个面值等于27，之后看子问题就是求n-1步的最少硬币数，有和求n步的问题一样了
  2. 转移方程
    以示例数据为例，用一个数组f[]来储存面值为i时的最少硬币数量，即可以推到出转移公式为：
    $f[27] = min{f[27-2]+1,f[27-5]+1,f[27-7]+1};$
  3. 考虑初始条件和边界情况
    这道题的初始条件应该时f[0] = 0,然后从f[1]开始计算
    边界情况应该考虑M-A[j]会不会小于零导致数组下标越界的问题,并且这道题会在如果f[i-A[j]]没有解的情况下设置为最大数,所以要判断f[i-A[j]]是否为最大数,是也不能有其计算
  4. 计算顺序
    就先计算面值为1,2,3…..M就好

具体代码实现

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
34
35
36
37
package Java.algorithm_study;

import java.util.Scanner;

class Coinnum {
    public static void main(String[] args) {
        int[] A = { 2, 5, 7 };
        Scanner scanner = new Scanner(System.in);
        int M = scanner.nextInt();

        //声明一个储存数组，用来记录不同状态的结果
        int[] F = new int[M + 1];
        //确定成员数组大小
        int n = A.length;

        //初始条件
        F[0] = 0;

        for (int i = 1; i <= M; i++) {//拼成银币为i元
            F[i] = Integer.MAX_VALUE;//先让i为无穷大
            for (int j = 0; j < n; j++) {
                if (i >= A[j] && F[i - A[j]] != Integer.MAX_VALUE) {
                    F[i] = Math.min(F[i],F[i-A[j]]+1);
                }
            }
        }

        if(F[M] == Integer.MAX_VALUE){
            System.out.println(-1);
        }
        else {
            System.out.println(F[M]);
        }
        
        scanner.close();
    }
}

机器人走方格

让机器人从矩阵方格的第一个位置开始出发,走到矩阵方格的右下角位置,矩阵方格为m*n,要求求从左上角走到右下角有多少种走法(只能向下移动或向右移动)
题目链接:
机器人走方格

问题分析

  1. 确定状态
    最后一步是走到(m-1,n-1)的位置,走到这个格子有两种可能即从(m-2,n-1)走过来,或者从(m-1,n-2)走过来,那么计算的子问题就是要求走到(m-2,n-1)和(m-1,n-2)的走法
    因为右两个状态,所以需要一个二维的数组用来储存状态
  2. 转移方程
    因为(m-1)(n-1)的可以从(m-2,n-1)和(m-1,n-2)两个位置走来,那么就是(m-2,n-1)和(m-1,n-2)的走法之和就可以得到转移方程为:
    $f[i][j] = f[i-1][j] + f[i][j-1]$;
  3. 初始条件和边界情况
    初始条件应该是$f[0][0] = 1$
    边界情况是i = 0时走法为1,因为只能一直向右走才能走到(不能向上走)
    同样j = 0时的一列的走法也为1
    即发$f[0][i] = f[j][0] = 1;$
    为了简化时间,直接在循环中初始化
  4. 计算顺序
    从左到右求出一行后再求下一行,这样$f[i][i]$的上一行已经求过了,即$f[i-1][j]$可以直接用了,在这一步的前面一步也已经求了$f[i][j-1]$了,转移方程需要的条件就都有了

具体代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package Java.algorithm_study;

public class Unique_paths {
    public static void main(String[] args) {
        int m = 3, n = 7;//题目条件,假设是3*7的矩阵
        
        //创建储存矩阵
        int[][] f = new int[m][n];

        //使用转移方程求解
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                //初始化边界情况
                if (i == 0 || j == 0) {
                    f[i][j] = 1;
                }else{
                    f[i][j] = f[i - 1][j] + f[i][j - 1];
                }
            }
        }
        System.out.println(f[m-1][n-1]);
    }
}