动态规划（一）

发表于 分类于
本文字数： 2k 阅读时长 ≈ 2 分钟

简介

动态规划，Dynamic Programming，简称DP。

特点

  • 最优子结构
  • 重叠子问题

解题一般思路

  1. 分解子问题：子问题与原问题相同/相似，只是缩小了规模，“大而化小，小而化了”。
  2. 确定状态：子问题各变量的一组取值
  3. 确定边界：初始状态，或者边界条件的取值
  4. 确定状态转移方程：递推的公式

关键是确定状态转移方程，在什么条件下进行什么状态的转换。

DP vs. 递归

  • 递归：自上而下，就会有重复的子问题
  • DP：自下而上，用空间换时间

🌰

  • 最长公共子序列LCS
  • 最长上升子序列

题目

首先从最简单的开始，通过斐波那契数列来感受重叠子问题。

斐波那契数列

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

给定 N，计算 F(N)。

显然，这个问题用递归求解很简单。

1
2
3
4
5
int fib(int N) {
    if (N == 0) return 0;
    if (N == 1) return 1;
    return fib(N - 1) + fib(N - 2);
}

附上力扣的题目链接https://leetcode-cn.com/problems/fibonacci-number/

假设N=6，画出递归树，可以发现有很多重复的子问题，也就是在求解的过程中进行了重复计算，增加了时间的开销。

N为6的递归树
N为6的递归树

我们把重复计算的地方存下来，“用空间换时间”，避免重复的计算。

1
2
3
4
5
6
7
8
9
10
int fib(int n) {
    int f[101];
    f[0] = 0;
    f[1] = 1;
    for (int i = 2; i <= n; ++i) {
        f[i] = f[i - 1] + f[i - 2];
        f[i] = f[i] % (1000000007);
    }
    return f[n];
}

附上力扣题目链接https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/

70. 爬楼梯

到达第n阶楼梯的方法数量 = 到达第n-1阶楼梯的方法总数 + 到达第n-2阶楼梯的方法总数 解释：最后一步可能走一个阶梯，也可能走两个阶梯 其实是一个斐波那契数列

  • 状态

d[i]表示达到第i阶的方法总数

  • 边界：

    d[0] = 1 实际上无这种情况，为递推定义的 d[1] = 1 n>=2时，进行状态转移

  • 状态转移方程：

d[n] = d[n - 1] + d[n - 2]

解题代码：

1
2
3
4
5
6
7
8
9
int climbStairs(int n){
    int d[101];
    d[0] = 1;
    d[1] = 1;
    for(int i = 2; i <= n; i++){
        d[i] = d[i - 1] + d[i - 2];
    }
    return d[n];
}

746. 使用最小花费爬楼梯

  • 分析过程

对于每个阶梯，都有选和不选，两种情况。

假设求d[9]，选择第9个阶梯，那么有两种情况：一是选择第7个阶梯，二是选择第8个阶梯。

...依次做下去。

使用最小花费爬楼梯的分析
使用最小花费爬楼梯的分析
  • 状态

d[i]代表到达i阶的最小花费，i=0和i=1的情况下特别处理

  • 边界

    n<2的时候，取min(cost[0], cost[1]); d[0] = cost[0]; d[1] = cost[1];

  • 结果

求的是到达n的前1阶或前2阶的最小值，即min(d[costSize - 2], d[costSize - 1]);

  • 状态方程
1
d[i] = min(d[i - 2] + cost[i], d[i - 1] + cost[i]); // 当 i >=2 时
  • 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//
// Created by Christy on 2020/7/25.
//
int min(int a, int b) {
    return a < b ? a : b;
}

int minCostClimbingStairs(int *cost, int costSize) {
    int *d = (int *) malloc(sizeof(int) * costSize);
   
    if (costSize < 2) {
        return min(cost[0], cost[1]);
    }

    d[0] = cost[0];
    d[1] = cost[1]; // 这里不能写min(min(cost[0], cost[1]);
    
    for (int i = 2; i < costSize; ++i) {
        d[i] = min(d[i - 2] + cost[i], d[i - 1] + cost[i]);
    }
    return min(d[costSize - 2], d[costSize - 1]);
}

经典问题的状态转移方程

动态规划问题 - 经典模型的状态转移方程

力扣上的一个关于DP的总结

https://leetcode.com/discuss/general-discussion/458695/dynamic-programming-patterns#Decision-Making