文章 标签 分类 关于

目录

动态规划算法

 收录于 算法
   约 2405 字   预计阅读 5 分钟    次阅读  

一般决策类问题（0-1背包问题）或者含有大量重叠的子问题（爬楼梯）会考虑用动态规划解题，通过寻找最优子结构来求解大问题的最终答案

1. 解题套路

1.1 明确dp数组含义

动态规划问题通过定义dp数组来记录解题过程中的最优子结构，dp数组的维度是由解题的需要来确定的，比如爬楼梯的问题，每次爬1层或爬2层，是一个一维的问题，定义dp[i]为爬上i阶楼梯的有dp[i]种方法；又比如在m x n的网格上向下走一步和向右走一步到达终点的方式，这是一个典型的dp[i][j]二维数组的问题,定义dp[i][j]表示为达到坐标为（i,j）的点，一共有dp[i][j]种方式

1.2 写出状态转移方程

状态转移方程就是要找出，爬1级，爬2级；向左走，向下走；对字符串的操作是增，删，改的不同策略和dp[i][j]的等式关系:

对于爬楼梯，需要找出一共有多少种策略：

1

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

对于不同路径问题，也是需要找到总共的路径数：

1

dp[i][j] = dp[i-1][j] + dp[i][j-1]

对于求编辑距离问题，需要找的是最小值,在前一操作的基础上，再进行一次操作：

1

dp[i][j]  = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) + 1

1.3 找出初始值

这里的初始值是在状态转移方程失效的情况下，dp数组对应的值，通常情况下是在dp数组的前面几个值，例如dp[0],dp[0][1...n],dp[1...n][0]情况下，dp数组的值

2 题目实战

2.1 简单一维数组dp问题

题目 : 70 爬楼梯

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

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

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

1
2
3
4
5
6
7
8

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。

1.  1 阶 + 1 阶
2.  2 阶
dp三板斧

  • 明确dp数组含义

    1

    dp[i]的含义就是爬上一个i阶的台阶共有dp[i]种方法

  • 状态转移方程

    1
2
3
4
5

    这里一共有两种爬楼梯的方式，爬1个台阶，或者爬2个台阶,我们已经定义了爬上一个i阶的台阶共有dp[i]种方法，那么当最后一次爬上了1个台阶或爬上了两个台阶，在这之前一共有多少种方式呢：
爬一个台阶：dp[i-1]
爬两个台阶：dp[i-2]
  
所以 dp[i][j] = dp[i-1] + dp[i-2]

  • 初始值

    1
2
3

    当n == 1时，只能有爬1级楼梯这1种方式
当n == 2时，只有爬2次1级楼梯和爬1次2级楼梯这两种方式
只有当n > 3时，才存在爬1级楼梯和爬2级楼梯的不同组合方式
代码
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func climbStairs(n int) int {
    if n <= 2{
        return n
    }
    // 1.定义dp数组
    dp := make([]int,n+1)
    // 2.base case
    dp[1] = 1
    dp[2] = 2
    
    // 3.状态转移方程
    for i:=3;i<=n;i++{
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}

2.2 中等难度二维数组dp问题

题目 ：62. 不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

https://assets.leetcode.com/uploads/2018/10/22/robot_maze.png

1
2

输入：m = 3, n = 7
输出：28
dp 三板斧
  • dp数组含义
1

这里涉及行跟列的网格，需要定义二维数组来分别表示向下走和向右走，dp[i][j]表示走到(i,j)这个格子共有dp[i][j]种走法
  • 状态转移方程
1
2
3
4

目的是走到(i,j)，只有向右走和向下走两种方式:
当我们在(i-1,j)时，向右走就能到达(i,j);
当我们在(i,j-1)时，向下走就能到达(i,j);
dp[i][j] = dp[i-1][j] + dp[i][j-1]
  • 初始情况
1
2
3

当i == 0 || j == 0时，状态转移方程时不成立的，因此我们在考虑i == 0 || j == 0 的时候,dp[i][j]的值为多少
当i == 0,表明当前状态只可能是前面所有状态向右移动一种方式而来，所以 dp[0][1...n] = 1
当j == 0,表明当前状态只可能是前面所有状态向下移动一种方式而来，所以 dp[1...n][0] == 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

func uniquePaths(m int, n int) int {
    if(m < 0 || n < 0 ){
        return 0
    }

    dp := make([][]int,m)
    for i,_ := range dp{
        dp[i] = make([]int,n)
    }
    // 1.base case
    // 1.1 在最上面一行
    // for i:=0; i< n;i++{
    //     dp[0][i] = 1

    // }
    // // 1.2 在最左侧一列
    // for i:=0;i<m;i++{
    //     dp[i][0] = 1
    // }
    // 2.状态转移方程
    for i := 0;i<m;i++{
        for j := 0;j<n;j++{
            if i == 0 || j == 0{
                dp[i][j] = 1
            }else{
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
            }
        }
    }
    return dp[m-1][n-1]
}

2.3 较难二维数组dp,状态超过3种情况

题目： 72.编辑距离

给你两个单词 word1 和word2，请你计算出将 word1 转换成 word2 所使用的最少操作数(编辑距离) 。

你可以对一个单词进行如下三种操作：

插入一个字符 删除一个字符 替换一个字符

示例 1：

1
2
3
4
5
6

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
dp三板斧

  • dp数组含义

    1

    dp[i][j]表示word1的前i个字母和word2的前j个字母之间的编辑距离

  • 状态转移方程

    1
2
3
4
5
6
7
8

    增删改对应3种状态
D[i][j-1] 为 A 的前 i 个字符和 B 的前 j - 1 个字符编辑距离的子问题。即对于 B 的第 j 个字符，我们在 A 的末尾添加了一个相同的字符，那么 D[i][j] 最小可以为 D[i][j-1] + 1；
  
D[i-1][j] 为 A 的前 i - 1 个字符和 B 的前 j 个字符编辑距离的子问题。即对于 A 的第 i 个字符，我们在 B 的末尾添加了一个相同的字符，那么 D[i][j] 最小可以为 D[i-1][j] + 1；
  
D[i-1][j-1] 为 A 前 i - 1 个字符和 B 的前 j - 1 个字符编辑距离的子问题。即对于 B 的第 j 个字符，我们修改 A 的第 i 个字符使它们相同，那么 D[i][j] 最小可以为 D[i-1][j-1] + 1。特别地，如果 A 的第 i 个字符和 B 的第 j 个字符原本就相同，那么我们实际上不需要进行修改操作。在这种情况下，D[i][j] 最小可以为 D[i-1][j-1]。
  
dp[i][j] = min(dp[i-1][j-1],min(dp[i][j-1],dp[i-1][j])) + 1

图解

绿色：增 红色：删 黄色：改

https://pic.leetcode-cn.com/36684da0c9884d45a3aa96e20dd99caf58e83d3ab0e0892195908137c2f9f57d-%E5%9B%BE%E7%89%87.png

  • 确定初始情况

    1
2

    当i == 0 时，表示将一个空串变为word2,我们只要依次插入就行了，所以 dp[0][i] = dp[0][i-1] + 1
当j == 0 时，表示word1变为一个空串，我们只要依次删除就行了，所以 dp[i][0] = dp[i-1][0] + 1

https://pic.leetcode-cn.com/62ea5e33d1ee2396c74c87941269bc1e53cd7385c341c49b160129f2e49de80e-%E5%9B%BE%E7%89%87.png

https://pic.leetcode-cn.com/d892c5f4463bc801dff85fed4c8b8e76ed0d178b1b917a4447b642c243d46c51-%E5%9B%BE%E7%89%87.png

动态规划表格练习地址

代码
 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
38
39
40
41

func minDistance(word1 string, word2 string) int {
    n1 := len(word1)
    n2 := len(word2)

    // n1和n2只要有一个是空串就最小次数就是另一个非空串的长度（只要全部拷贝过去）
    if n1* n2 == 0{
        return n1 + n2
    }

    dp := make([][]int,n1 + 1)
    for i,_ := range dp{
        dp[i] = make([]int,n2 + 1)
    }

    // base case
    for i := 1;i < n1;i++{
        dp[i][0] = dp[i-1][0] + 1
    }
    for j := 1; j < n2;j++{
        dp[0][j] = dp[0][j-1] + 1
    }

    for i:=1;i<=n1;i++{
        for j:=1;j<=n2;j++{
            if word1[i-1] == word2[j-1]{
                dp[i][j] = dp[i-1][j-1]
            }else{
                dp[i][j] = min(dp[i-1][j-1],min(dp[i][j-1],dp[i-1][j])) + 1
            }
        }
    }

    return dp[n1][n2]
}

func min(a,b int)int{
    if a < b{
        return a
    }
    return b
}
更新于 2021-07-14
阅读原始文档
 动态规划, 最优子结构, 决策类问题, 状态转移方程
返回 | 主页