动态规划

2020-12-11  本文已影响0人  hellomyshadow

【动态规划】，Dynamic Programming, DP
过程：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以这种多阶段最优化决策解决问题的过程 称为【动态规划】

思路

【动态规划】是一种特殊的分治，与【分治算法】的思路类似：

由于【动态规划】解决的问题有重叠子问题的特点，为了让每个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中，即 以空间换时间

与【分治算法】最大的区别是：适合于用【动态规划】求解的问题，经分解后得到的子问题往往【不是互相独立的】，即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解。

特性

采用【动态规划】求解的问题通常具备三个特性：

基本步骤

【动态规划】所处理的问题是一个 多阶段决策的问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。
这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线（通常是求最优活动路线）

初始状态 -> |决策-1| -> |决策-2| -> ... -> |决策-n| -> 结束状态
确定动态规划的三要素：

递推关系 必须是从【次小问题】开始到【较大问题】之间的转化，从这个角度来讲，【动态规划】往往可以用递归程序来实现，不过因为递推可以充分利用前面保存的子问题的解来减少重复计算，所以对于大规模问题来说，有递归不可比拟的优势，这也就是【动态规划算法】的核心之处。

确定了【动态规划】的三要素之后，整个求解过程就可以用一个【最优决策表】来描述，最优决策表是一个二维表（或一维表）。其中，行表示决策的阶段，列表示问题的状态。表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值（如最短路径、最长公共子序列、最大价值等），填表的过程就是根据递推关系，从1行1列开始，以行或列优先的顺序，一次填写表格，最后根据整个表格的数据、通过简单的取舍或运算求得问题的最优解。

f(n, m) = max{ f(n-1, m), f(n-1, m - w[n]) + P(n, m) }

动态规划的解题套路

【动态规划】无非就是利用 历史记录 来避免重复计算，而这些历史记录一般使用 一维数组 或 二维数组 来保存。

一维数组 之 青蛙跳台阶

正常青蛙

问题：一只青蛙一次跳 1 个台阶，也可以跳 2 个台阶，请问 跳 N 个台阶有多少种跳法？

# 迭代版本
function jump(n){
    if(n <= 2){
        return n;
    }
    // 假装使用数组：这样会造成空间复杂度为 O(n)
    // 其实可以直接使用 【变量】 代替，这样空间复杂度优化成 O(1)
    let dp = [0, 1, 2]
    for(let i = 3; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}

# 递归版本
function jump(n, start = 1, end = 1){
    if(n <= 2){
        return n
    }
    return jump(n - 1) + jump(n - 2)
}

# 尾递归优化
function jump(n, start = 1, end = 0){
    if(n === 0){
        return end;
    } else if(start === 0) {
        start = 1
    }
    return jump(n - 1, end, start + end);
}
变异青蛙

问题：一只青蛙一次跳 1 个台阶，也可以跳 2 个台阶、3个台阶、4个台阶、...、n个台阶，请问 跳 N 个台阶有多少种跳法？
分析：同理，跳上 n 级台阶有 n 种跳法，f(n) = f(n-1) + f(n-2) + ... + f(1)
又由 f(n-1) = f(n-2) + f(n-3) + ... + f(1) 可知，f(n) = 2f(n-1) = 2^(n-1)*f(1) = 2^(n-1)*1
得：f(n) = 2^(n-1)，n > 2。当n <= 2 时，f(n) = n

二维数组

其实，【动态规划】解题时大多数使用的都是 二维数组

机器人走方格（路径规划）

一个机器人位于 M x N 网格的左上角，每次只能向下或向右移动一步，到达网格右下脚一共有多少条不同的路径？

机器人走网格 
public int solution(int m, int n) {
    int[][] dp = new int[m][n];

    for (int i = 0; i < m; i++) {
        dp[i][0] = 1;
    }
    for (int i = 0; i < n; i++) {
        dp[0][i] = 1;
    }
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m - 1][n - 1];
}

空间复杂度的优化：由状态转移方程式dp[i][j] = dp[i-1][j] + dp[i][j-1] 可知，当填充第 i 行的值时，只需要知道第i-1行的值，从第1行到第i-2行都是不需要的！
https://zhuanlan.zhihu.com/p/91582909

进阶版

保持问题的题意，在网格中增加障碍物，机器人无法越过障碍物
分析：虽然增加了障碍物，但关系式还是适用的，不过需要些许改变

// 给定一个二维数组，如果某个元素值为 1，表示有障碍物
public int uniquePathsWithObstacles(int[][] matrix) {
    if(matrix == null) return 0;
    if(matrix[0][0] == 1) {  // 起点有障碍物，不可达
        return 0;
    }
    int row = matrix.length;
    int col = matrix[0].length;
    if(matrix[row-1][col-1] == 1) {  // 重点有障碍物，不可达
        return 0;
    }
    // 构建路径二维数组
    int[][] dp = new int[row][col];
    // 初始化起点，开始有 1 条路径
    dp[0][0] = 1;
    // 第一列: 初始化值都是 1
    for(int i = 1; i < row; i++) {
        if(matrix[i][0] != 1) {  // 没有障碍物
            dp[i][0] = dp[i-1][0];
        }
    }
    // 第一行: 初始化值都是 1
    for(int j = 1; j < col; j++) {
        if(matrix[0][j] != 1) {  // 没有障碍物
            dp[0][j] = dp[0][j-1];
        }
    }
    // 计算其他所有路径
    for(int i = 1; i < row; i++) {
        for(int j = 1; j < col; j++) {
            if(matrix[i][j] == 1) continue;  // 障碍物
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[row-1][col-1];
}

最小路径之和

给定一个M x N的网格，每次只能向下或向右移动一格，请找出一条从左上角到左下角的路径，使得路径上的数字总和最小。

arr = [
    [1, 3, 1],
    [1, 5, 1],
    [4, 2, 1]
]
// 最小路径 1 -> 3 -> 1 -> 1 -> 1，总和为 7

public int uniquePath(int[][] arr) {
    int row = arr.length;
    if(row == 0) return 0;
    int col = arr[0].length;
    if(col == 0) return 0;
    
    int[][] dp = new int[row][col];
    // 初始化
    dp[0][0] = arr[0][0];
    // 第一列的初始化
    for(int i = 1; i < row; i++) {
        dp[i][0] = dp[i-1][0] + arr[i][0];
    }
    // 第一行的初始化
    for(int j = 1; j < col; j++) {
        dp[0][j] = dp[0][j-1] + arr[0][j];
    }
    // 推导 dp[row-1][col-1]
    for(int i = 1; i < row; i++) {
        for int j = 1; j < col; j++) {
            dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + arr[i][j];
        }
    }
    return dp[row-1][col-1];
}
// O(n*m) 的空间复杂度可以优化成 O(min(n, m)) 的空间复杂度

编辑距离

给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数？
可以对一个单词进行三种操作：

# 举个栗子
word1 = "horse", word2 = "ros"
// 最小操作数 3
horse -> rorse (将 h 替换成 r)
rorse -> rose  (删除 r)
rose  -> ros   (删除 e)
步骤一：定义数组元素的含义

目的是求 word1 转换成 word2 所使用的最少操作数，那么就定义 dp[i][j] 的含义为：当字符串word1 的长度为i、字符串word2 的长度为j 时，将 word1 转为 word2 所使用的最少操作数为dp[i][j]。

步骤二：数组元素之间的关系式

关系式的推导往往是从小规模到大规模的过程，也就是说，dp[i][j] 通常都会与 dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1] 存在某种关系。
分析：
由题可知：对 word1 的操作有三种：插入、删除、替换 一个字符
要想让操作的次数最小，就要寻找最佳操作：

至此，通过三种操作得到了三种dp[i][j]的关系式，并且利用了之前保存的状态，所以只需要 取其中最少的步数 即可的得到原问题的解。
总关系式：

dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
步骤三：初始值

数组角标不能为负数，而当 i=0 或 j=0 时，关系式中的 i - 1 和 j - 1 就得到了负数的角标。所以，初始值就是计算出所有dp[0][0...j]和所有的dp[0...i][0]。
由二维数组dp 的含义可知，角标表示两个字符串的长度，当i=0 或 j=0时，也就是有一方字符串的长度为0，那么只需要 删除 或 插入 操作即可。

实现代码
function convert(s1, s2) {
    let m = s1.length
    let n = s2.length
    // 构建二维数组：长度比字符串大 1，是因为关系式的角标不能为 0
    let dp = new Array(m+1).fill(new Array(n+1))
    // dp[0...m][0] 初始化
    for(let i = 0; i < m+1; i++) {
        dp[i][0] = i
    }
    // dp[0][0...n] 初始化
    for(let j = 0; j < n+1; j++) {
        dp[0][j] = j
    }
    // 数组元素之间的关系
    for(let i = 1; i < m+1; i++) {
        for(let j = 1; j < n+1; j++) {
            if(s1[i-1] === s2[j-1]) {
                // 两个字符相等，则无需操作，即操作步数与前一步相等
                dp[i][j] = dp[i-1][j-1]
            } else {
                // 取最小操作步数 + 1 就是当前操作步数
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
            }
        }
    }
    return dp[m][n]
}
上一篇下一篇

猜你喜欢

热点阅读