Skip to content

Latest commit

 

History

History
485 lines (388 loc) · 15 KB

动态规划.md

File metadata and controls

485 lines (388 loc) · 15 KB

动态规划

背景

先从一道题目开始~

如题 triangle

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

[
    [2],
   [3,4],
  [6,5,7],
 [4,1,8,3]
]

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

使用 DFS（遍历 或者 分治法）

超时

var row = 0;

var minimumTotal = function(tringle){
    row = tringle.length;
    return helper(0,0,tringle);
}

var helper = function(level, c, tringle){
    if (level === row-1) {
        return tringle[level][c];
    }
    let left = helper(level+1, c, tringle);
    let right = helper(level+1, c+1, tringle);
    return Math.min(left,right) + tringle[level][c];
}

let tringle = [
    [2],
   [3,4],
  [6,5,7],
 [4,1,8,3]
];

console.log(minimumTotal(tringle)); //11

动态规划就是把大问题变成小问题，并解决了小问题重复计算的方法称为动态规划

动态规划和 DFS 区别

  • 二叉树子问题是没有交集，所以大部分二叉树都用递归或者分治法，即DFS，就可以解决。
  • 像 triangle 这种是有重复走的情况，子问题是有交集，所以可以用动态规划来解决。

动态规划三个特性：

  • 最优子结构

    最优子结构指的是，问题的最优解包含子问题的最优解。反过来说就是，我们可以通过子问题的最优解，推导出问题的最优解。如果我们把最优子结构，对应到我们前面定义的动态规划问题模型上，那我们也可以理解为，后面阶段的状态可以通过前面阶段的状态推导出来。

  • 无后效性

    无后效性有两层含义，第一层含义是，在推导后面阶段的状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型，其实基本上都会满足无后效性。

  • 重复子问题

    如果用一句话概括一下，那就是，不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。所以才会用一个数组记录中间结果，避免重复计算。

动态规划，自底向上

这里变成一位数组，因为层号实际上可以不用记录，每次记录上一层的值，到当前层就把以前的覆盖到，动态规划运用场景其中一条就是最优子结构，往下走不用回头一定是最优的。

f(i,j)=min(f(i+1,j),f(i+1,j+1))+triangle[i][j]

var minimumTotal = function(tringle){
    let row = tringle.length;
    let dp = new Array(row+1).fill(0);
    for (let level = row-1;level>=0;level--){
        for (let i = 0; i <= level; i++) { //第i行有i个数
            dp[i] = Math.min(dp[i],dp[i+1]) + tringle[level][i];
        }
    }
    return dp[0];
}

function minimumTotal(triangle: number[][]): number {  // 时间、空间复杂度O（n2）
    const len = triangle.length
    const ans: number[][] = new Array(len).fill(0).map(() => new Array(len).fill(0))
    ans[0][0] = triangle[0][0]
    for (let i = 1; i < len; i++) {
        ans[i][0] = ans[i - 1][0] + triangle[i][0]
        for (let j = 1; j < triangle[i].length; j++) {
            ans[i][j] = Math.min(ans[i - 1][j], ans[i - 1][j - 1]) + triangle[i][j]
        }
        ans[i][i] = ans[i - 1][i - 1] + triangle[i][i]
    }
    return Math.min(...ans[len - 1])
};

递归和动规关系

递归是一种程序的实现方式：函数的自我调用

Function(x) {
	...
	Funciton(x-1);
	...
}

动态规划：是一种解决问题的思想，大规模问题的结果，是由小规模问题的结果运算得来的。动态规划可用递归来实现(Memorization Search)。

使用场景

满足三个条件：最优子结构，无后效性，重复子问题

简单来说就是：

  • 满足以下条件之一
    • 求最大/最小值（Maximum/Minimum ）
    • 求是否可行（Yes/No ）
    • 求可行个数（Count(*) ）
  • 满足不能排序或者交换（Can not sort / swap ）

如题：longest-consecutive-sequence 位置可以交换，所以不用动态规划

四点要素

  1. 状态 State
    • 灵感，创造力，存储小规模问题的结果
  2. 方程 Function
    • 状态之间的联系，怎么通过小的状态，来算大的状态
  3. 初始化 Intialization
    • 最极限的小状态是什么， 起点
  4. 答案 Answer
    • 最大的那个状态是什么，终点

常见四种类型

  1. Matrix DP (10%)
  2. Sequence (40%)
  3. Two Sequences DP (40%)
  4. Backpack (10%)

注意点

  • 贪心算法大多题目靠背答案，所以如果能用动态规划就尽量用动规，不用贪心算法

1、矩阵类型（10%）

64. 最小路径和

给定一个包含非负整数的 *m* x *n* 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。**说明：**每次只能向下或者向右移动一步。

var minPathSum = function (grid) {
    let m = grid.length
    let n = grid[0].length
    for (let i = 1; i < m; i++) {
        grid[i][0] += grid[i - 1][0]
    }
    for (let i = 1; i < n; i++) {
        grid[0][i] += grid[0][i - 1]
    }
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j]
        }
    }
    return grid[m - 1][n - 1]
};
62. 不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？

var uniquePaths = function (m, n) {
    let dp = new Array(m).fill(new Array(n).fill(1)) //第一行和第一列都是1
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        }
    }
    return dp[m - 1][n - 1]
};
63. 不同路径 II

同上，不过增加了障碍物。

思路：第一行（列）遇到障碍物之前置为1，之后置为0（包括障碍物）

var uniquePathsWithObstacles = function (obstacleGrid) {
    let m = obstacleGrid.length
    let n = obstacleGrid[0].length
    if (obstacleGrid[0][0] === 1) {
        return 0
    }
    for (let i = 0; i < m; i++) {
        if (obstacleGrid[i][0] === 1) {
            for (let j = i; j < m; j++) {
                obstacleGrid[j][0] = 0
            }
            break
        }
        obstacleGrid[i][0] = 1
    }
    for (let i = 1; i < n; i++) {
        if (obstacleGrid[0][i] === 1) {
            for (let j = i; j < n; j++) {
                obstacleGrid[0][j] = 0
            }
            break
        }
        obstacleGrid[0][i] = 1
    }
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            if (obstacleGrid[i][j] === 1) {
                obstacleGrid[i][j] = 0
            } else {
                obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]
            }
        }
    }
    return obstacleGrid[m - 1][n - 1]
};

2、序列类型（40%）

Sequence

70. 爬楼梯
var climbStairs = function (n) {
    const res = [1, 2]
    for (let i = 2; i < n; i++) {
        res[i] = res[i - 1] + res[i - 2]
    }
    return res[n - 1]
};
55. 跳跃游戏

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。

var canJump = function (nums) {
    let k = 0
    for (let i = 0; i < nums.length; i++) {
        if (i > k) { return false }
        k = Math.max(k, i + nums[i])
    }
    return true
};
45. 跳跃游戏 II

使用最少的跳跃次数到达数组的最后一个位置。

function jump(nums: number[]): number {  //从后往前推
    let pos: number = nums.length - 1
    let step: number = 0
    while (pos > 0) {
        for (let i = 0; i < pos; i++) {
            if (i + nums[i] >= pos) { //第一次到达终点的位置，然后往前找能到达该位置的点。
                pos = i
                step++
                break
            }
        }
    }
    return step
};
function jump(nums: number[]): number {  //从前往后推
    let maxPos: number = 0
    let step: number = 0
    let end: number = 0
    for (let i = 0; i < nums.length - 1; i++) {
        maxPos = Math.max(i + nums[i], maxPos)
        if(i === end) {
            end = maxPos
            step++
        }
    }
    return step
};
132. 分割回文串 II

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。返回符合要求的 最少分割次数 。

300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

function lengthOfLIS(nums: number[]): number {
    let dp: number[] = new Array(nums.length).fill(1)
    for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1)
            }
        }
    }
    return Math.max(...dp)
};
139. 单词拆分

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

function wordBreak(s: string, wordDict: string[]): boolean {
    const len: number = s.length
    const dp: boolean[] = new Array(len + 1).fill(false)
    const wordDictSet: Set<string> = new Set(wordDict)
    dp[0] = true
    for (let i = 1; i <= len; i++) {
        for (let j = 0; j < i; j++) {
            if (dp[j] && wordDictSet.has(s.slice(j, i))) {
                dp[i] = true
                break
            }
        }
    }
    return dp[len]
};

Two Sequences DP

1143. 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

function longestCommonSubsequence(text1: string, text2: string): number {
    const col: number = text1.length
    const row: number = text2.length
    const dp: number[][] = new Array(row + 1).fill(0).map(() => new Array(col + 1).fill(0))
    for (let i = 1; i <= row; i++) {
        for (let j = 1; j <= col; j++) {
            if (text2[i - 1] === text1[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])
            }
        }
    }
    return dp[row][col]
};
72. 编辑距离

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

function minDistance(word1: string, word2: string): number {
    let l1: number = word1.length
    let l2: number = word2.length
    let dp: number[][] = new Array(l1 + 1).fill(0).map(() => new Array(l2 + 1).fill(0))
    for (let i = 0; i <= l1; i++) {
        dp[i][0] = i
    }
    for (let j = 0; j <= l2; j++) {
        dp[0][j] = j
    }
    for (let i = 1; i <= l1; i++) {
        for (let j = 1; j <= l2; j++) {
            if (word1[i - 1] === word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1]
            } else {
                dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
            }
        }
    }
    return dp[l1][l2]
};

零钱和背包（10%）

322. 零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

function coinChange(coins: number[], amount: number): number {
    const dp: number[] = new Array(amount + 1).fill(amount + 1)
    dp[0] = 0
    for (let i = 1; i <= amount; i++) {
        for (let j = 0; j < coins.length; j++) {
            if (i - coins[j] >= 0) {
                dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1)
            }
        }
    }
    if (dp[amount] > amount) {
        return -1
    }
    return dp[amount]
};
92.背包问题

在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为Ai

function backpack(m: number, A: number[]): number {
	const dp: boolean[][] = new Array(A.length+1).fill(false).map(()=>new Array(m+1).fill(false))
	for(let i=1;i<=A.length;i++){
        for(let j=0;j<=m;j++){
            dp[i][j] = dp[i-1][j]
            if(j-A[i-1] >= 0 && dp[i-1][j-A[i-1]]){
                dp[i][j] = true
            }
        }
    }
    for(let i=m;i>=0;i--){
        if(dp[A.length][i]){
            return i
        }
    }
    return 0
}

练习

Matrix DP (10%)

Sequence (40%)

Two Sequences DP (40%)

Backpack & Coin Change (10%)