彭诗亮的博客

0%

动态规划基础算法分析

发表于

什么是动态规划

动态规划，英文:Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使 用动态规划是最有效的。

动态规划的解题步骤

结合自己之前的经历分析，做动规题目的时候，只是把递归推导公式推出来就拉到了，然后就开始解题，提交题目的时候经常发现解题总是会出现一些细节问题，比如dp数组初始化不对，或者遍历的数组对象有问题等等…甚至很多时候把题目AC之后，都不太清楚dp[i]表示的是什么。
这就是一种朦胧的状态，然后就把题给过了，遇到稍稍难一点的，可能直接就不会了，然后 看题解，然后继续照葫芦画瓢陷入这种恶性循环中。
最近看了Carl的动态规划分析专栏，对这套算法体系有了一定的理解，并对解题思路进行了总结

对于动态规划问题，可拆解为如下五步曲，这五步都搞清楚了，才能说把动态规划真的掌握了!

  1. 确定dp数组(dp table)以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

动态规划入门题目分析

斐波那契数列

斐波那契数
通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后 面的每一项数字都是前面两项数字的和。也就是:

1
2
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给你n ，请计算 F(n) 。

示例 1:

1
2
3
输入:2
输出:1
解释:F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2:

1
2
输入:3 输出:2
解释:F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3:

1
2
3
输入:4
输出:3
解释:F(4) = F(3) + F(2) = 2 + 1 = 3

提示:0 <= n <= 30

思路

这道题比较简单，题目中已经给出了递推公式，所以不需要分析，直接实现即可

dp5部曲

按照动态规划5部曲进行分析

  1. 确定dp数组以及下标的含义：表示第i个数的斐波那契数值dp[i]
  2. 确定递推公式 dp[i] = dp[i - 1] + dp[i - 2]
  3. dp数组如何初始化 dp[0] = 0, dp[1] = 1
  4. 确定遍历顺序 由于要保证第i个数的值为前两个数的和，所以要正向遍历
  5. 举例推导dp数组 打印dp数组应该是1,1,2,3,5,8,13,21…

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func Fib(n int) int {
    if n == 0 {
        return 0
    }
    if n == 1 {
        return 1
    }
    var dp = make([]int, n+1)
    dp[0] = 0
    dp[1] = 1
    for i := 2; i <= n; i++ {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}
  • 时间复杂度O(n)
  • 空间复杂度O(n)

动态规划题目一般往往可以优化空间复杂度，本道题也一样，可以将dp[0]、dp[1]作为两个变量值指针，然后用sum接收一下两个变量的和，在对dp[0]、dp[1]进行前移dp[0] = dp[1],dp[1] = sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func Fib(n int) int {
    if n == 0 {
        return 0
    }
    if n == 1 {
        return 1
    }
    var dp, sum = [2]int{0, 1}, 0
    for i := 2; i <= n; i++ {
        sum = dp[0] + dp[1]
		dp[0] = dp[1]
		dp[1] = sum
    }
    return sum
}
  • 时间复杂度O(n)
  • 空间复杂度O(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

思路

爬到第一层楼梯有一种方法，爬到二层楼梯有两种方法。

那么第一层楼梯再跨两步就到第三层 ，第二层楼梯再跨一步就到第三层。

所以到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来，那么就可以想 到动态规划了。

dp5部曲

动态规划5步

  1. 确定dp数组以及下标的含义：表示爬到第n阶有dp[n]种爬法的
  2. 确定递推公式
    首先是dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法，那么再一步跳一个台阶不就是dp[i]了
    么。
    还有就是dp[i - 2]，上i-2层楼梯，有dp[i - 2]种方法，那么再一步跳两个台阶不就是dp[i]了 么。
    那么dp[i]就是 dp[i - 1]与dp[i - 2]之和!
    所以dp[i] = dp[i - 1] + dp[i - 2] 。
  3. dp数组如何初始化 dp[0] = 1, dp[1] = 1, dp[2] = 2
  4. 确定遍历顺序 从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，遍历顺序一定是从前向后遍历的
  5. 举例推导dp数组 打印dp数组应该是1,2,3,5,8

通过dp5步分析后，得知这道题其实就是实现斐波那契数列，题目立马变得清晰了，这也是动态规划分析的重要性!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func ClimbStairs(n int) int {
	if n == 1 || n == 0 {
		return 1
	}
	if n == 2 {
		return 2
	}
	var dp [3]int
	dp[1] = 1
	dp[2] = 2
	sum := 0
	for i := 3; i <= n; i++ {
		sum = dp[1] + dp[2]
		dp[1] = dp[2]
		dp[2] = sum
	}
	return sum
}
  • 时间复杂度O(n)
  • 空间复杂度O(1)

使用最小花费爬楼梯

使用最小花费爬楼梯
数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i](下标从 0 开始)。

每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向 上爬一个阶梯或者爬两个阶梯。

请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。

示例 1：

1
2
3
4
5
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
  总花费为 15 。

示例 2：

1
2
3
4
5
6
7
8
9
10
输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
  总花费为 6 。

提示：

1
2
2 <= cost.length <= 1000
0 <= cost[i] <= 999

思路

这道题目可以说是昨天动态规划:爬楼梯的花费版本。 注意题目描述:每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，

你就可以选择向上爬一个阶梯或者爬两个阶梯

所以示例1中只花费一个15 就可以到阶梯顶，最后一步可以理解为 不用花费。

img.png

dp五部曲

动态规划5步

cost = [0：10,1：15,2：20]

  1. 确定dp数组以及下标的含义：dp[i]到达第i个台阶(顶层)的最小花费
  2. 确定递推公式
    由题目可知，最小花费方案分为从第i-1阶走1步，或者从第i-2阶走2步到达两种方案
    而不管选那种方案，由于最后一步一定要走，只不过选择的方案不同，所以，我的dp[i]都要固定花费cost[i]
    所以dp[i] = dp[i-1] + cost[i -1]或者dp[i] = dp[i-2] + cost[i - 2]
    最后的最小花费为dp[i] = min(dp[i-1] + cost[i -1], dp[i-2] + cost[i - 2]) + 0
    可得出爬i阶楼梯的最小花费为倒数第一步和倒数第二步的最小值 + 最后一步花费的费用
    dp[i] = min(dp[i - 1], dp[i -2]) + cost[i]
  3. dp数组如何初始化
    那么看一下递归公式，dp[i]由dp[i-1]，dp[i-2]推出，既然初始化所有的dp[i]是不可能的，
    那么只初始化dp[0]和dp[1]就够了，其他的最终都是dp[0]dp[1]推出。
  4. 确定遍历顺序 从递推公式dp[i]由dp[i - 1]和dp[i - 2]推导出的，所以遍历顺序一定是从前向后遍历的
  5. 举例推导dp数组 题目中打印dp数组应该是
    题目中共有3阶
    1
    2
    3
    4
    dp[0] = 0 + cost[0] = 10
    dp[1] = 0 + cost[1] = 15
    dp[2] = min(dp[1], dp[0]) + cost[2] = 30
    dp[3] = min(dp[2], dp[1]) + cost[3] = 15 // cost[3] = 0
    dp[3]为我们最后返回的结果

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func MinCostClimbingStairs(cost []int) int {
	var dp = make([]int, len(cost))
	dp[0] = 0 + cost[0]
	dp[1] = 0 + cost[1]
	for i := 2; i < len(cost); i++ {
		dp[i] = min(dp[i-1], dp[i-2]) + cost[i]
	}
	// 这里实际上是dp[3] = min(dp[2], dp[1]) + cost[3] = 15, cost[3]=0所以被我们省略了
	return min(dp[len(cost)-1], dp[len(cost)-2])
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
  • 时间复杂度O(n)
  • 空间复杂度O(n)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    func MinCostClimbingStairsPlus(cost []int) int {
       var dp0 = 0 + cost[0]
       var dp1 = 0 + cost[1]
       for i := 2; i < len(cost); i++ {
          dpi := min(dp0, dp1) + cost[i]
          dp0 = dp1
          dp1 = dpi
       }
       return min(dp0, dp1)
    }

优化空间复杂度后

  • 时间复杂度O(n)
  • 空间复杂度O(1)