vlambda博客
学习文章列表

漫画:动态规划系列 第一讲

0 1
概念讲解



漫画:动态规划系列 第一讲

    讲解动态规划的资料很多,官方的定义是指把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解。概念中的各阶段之间的关系,其实指的就是状态转移方程。很多人觉得DP难(下文统称动态规划为DP),根本原因是因为DP区别于一些固定形式的算法(比如DFS、二分法、KMP),没有实际的步骤规定第一步第二步来做什么,所以准确的说,DP其实是一种解决问题的思想。

    这种思想的本质是:一个规模比较大的问题(可以用两三个参数表示的问题),可以通过若干规模较小的问题的结果来得到的(通常会寻求到一些特殊的计算逻辑,如求最值等)

漫画:动态规划系列 第一讲    所以我们一般看到的状态转移方程,基本都是这样:





opt :指代特殊的计算逻辑,通常为max or min。

i,j,k 都是在定义DP方程中用到的参数。


dp[i] = opt(dp[i-1])+1

dp[i][j] = w(i,j,k) + opt(dp[i-1][k])

dp[i][j] = opt(dp[i-1][j] + xi, dp[i][j-1] + yj, ...)

    每一个状态转移方程,多少都有一些细微的差别。这个其实很容易理解,世间的关系多了去了,不可能抽象出完全可以套用的公式。所以我个人其实不建议去死记硬背各种类型的状态转移方程。但是DP的题型真的就完全无法掌握,无法归类进行分析吗?我认为不是的。在本系列中,我将由简入深为大家讲解动态规划这个主题。

    

    我们先看上一道最简单的DP题目,熟悉DP的概念:

漫画:动态规划系列 第一讲
第70题:假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
漫画:动态规划系列 第一讲

注意:给定 n 是一个正整数。

示例 1:

输入: 2输出: 2解释: 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2:

输入: 3输出: 3解释: 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶
02
题目图解


漫画:动态规划系列 第一讲

    通过分析我们可以明确,该题可以被分解为一些包含最优子结构的子问题,即它的最优解可以从其子问题的最优解来有效地构建。满足将大问题分解为若干个规模较小的问题”的条件我们令 dp[n] 表示能到达第 n 阶的方法总数,可以得到如下状态转移方程:


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






  • 上 1 阶台阶:有1种方式。

  • 上 2 阶台阶:有1+1和2两种方式。

  • 上 3 阶台阶:到达第3阶的方法总数就是到第1阶和第2阶的方法数之和。

  • 上 n 阶台阶,到达第n阶的方法总数就是到第 (n-1) 阶和第 (n-2) 阶的方法数之和。

    漫画:动态规划系列 第一讲

03
Go语言示例


根据分析,得到代码如下:


 1func climbStairs(n int) int {
2    if n == 1 {
3        return 1
4    }
5    dp := make([]int, n+1)
6    dp[1] = 1
7    dp[2] = 2
8    for i := 3; i <= n; i++ {
9        dp[i] = dp[i-1] + dp[i-2]
10    }
11    return dp[n]
12}




注:本系列所有教程中都不会用到复杂的语言特性,大家不需要担心没有学过go。算法思想最重要,使用go纯属本人爱好。同时,本系列所有代码均在leetcode上进行过测试运行,保证其严谨性!





温馨提示



浩仔讲算法~

每天一起学习图解漫画算法。

一起刷题,一起成长!

关注后有资源~