算法基本思想之动态规划

# 动态规划（dynamic programing）

动态规划被认为是一种与递归相反的技术。递归是从顶部开始将问题分解，通过解决掉所有分解出小问题的方式，来解决整个问题。动态规划解决方案从底部开始解决问题，将所有小问题解决掉，然后合并成一个整体解决方案。(自下而上)

动态规划中的三个重要的概念：

最优子结构
边界
状态转移公式

# 题目1

有一座高度是10级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法。

思路：10级台阶的所有走法可以根据最后一步的不同而分成两部分，最后一步可以是2级台阶也可以是1级台阶。假如是1级，前面9级台阶的走法数量取值为 X;假如是2级，前面8级台阶的走法数量取值为 Y。那么则有总的走法数量为 X+Y，即 F(10)=F(9)+F(8),从而推断出

F(1)=1
f(2)=2
F(n)=F(n-1)+F(n-2)(n>=3)

1
2
3

此题F(9)和 F(8) 是 F(10)的最优子结构。 F(1)和F(2) 是问题的边界。F(n)=F(n-1)+F(n-2)是状态转移方程。

方法1 递归求解

// 时间复杂度为 O(2^n)
function getClimbingWays (n) {
    if (n<3) {
        return n
    }
    return getClimbingWays(n - 1) + getClimbingWays(n - 2)
}

1
2
3
4
5
6
7

方法2 备忘录算法

 //时间复杂度为 O(n)
function getClimbingWays (n, obj = {}) {
    if (n < 3) {
        return n
    }
    if (obj[n]) {
        return obj[n]
    } else {
        const value = getClimbingWays(n - 1) + getClimbingWays(n - 2)
        obj[n] = value;
        return value;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13

方法3 迭代

 //时间复杂度为 O(n)
function getClimbingWays1 (n, obj = {}) {
    if (n < 3) {
        return n
    }
    let count1 = 1;
    let count2 = 2;
    let total = 0
    for (let i = 3; i <= n; i++) {
        total = count1 + count2;
        count1 = count2;
        count2 = total;
    }
    return total
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 题目2 计算斐波那契数列

方法1 递归

function recurFib (n) {
    if (n < 2) {
        return n;
    } else {
        return recurFib(n - 1) + recurFib(n - 2)
    }
}

1
2
3
4
5
6
7

方法2 迭代

function recurFib (n) {
    if (n < 2) {
        return n;
    } else {
        let last = 1, nextLast = 1, result = 1;
        for (let i = 2; i <= n; i++) {
            result = last + nextLast;
            last = nextLast;
            nextLast = result;
        }
        return result;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13

# 题目3、寻找最长公共字串

第一步,将问题分解。将两个字符串分解为成每个字符。
第二步,用一个2维数组去存放这两个字符串，并以 0 去初始化二维数组。

const len1=str1.length;
const len2=str2.length;
//初始化二维数组 。行和列都多加了一个并且都是0，属于占位符，这是为了判断上一个是否相等的操作
const arr = new Array(len1 + 1);
for (let i = 0; i <= len1 + 1; i++) {
    arr[i] = new Array(len2 + 1);
    for (let j = 0; j <= len2 + 1; j++) {
        arr[i][j] = 0;
    }
}

1
2
3
4
5
6
7
8
9
10

第三步，如果两个数组中的字符相等则加 1。

//比较二维数组中的相同字符
let maxLen = 0;//用于表示连续相等的子串的长度
let index = 0;//表示在str1和str2中相同字符的最大索引
for (let i = 1; i <= len1; i++) {
    for (let j = 1; j <= len2; j++) {
        //判断连续的两个字符是否相等，相等则加1
        if (str1[i] == str2[j] && str1[i - 1] == str2[j - 1]) {
            arr[i][j] = arr[i - 1][j - 1] + 1;
        }
        //求取最大子串的长度以及在str1中的索引值
        if (arr[i][j] > maxLen) {
            maxLen = arr[i][j];
            index = i;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

求解完整代码

function lcs (str1, str2) {
    const len1 = str1.length, len2 = str2.length;
    //初始化二维数组
    const dp = new Array(len1 + 1);
    for (let i = 0; i <= len1 + 1; i++) {
        dp[i] = new Array(len2 + 1);
        for (let j = 0; j <= len2 + 1; j++) {
            dp[i][j] = 0;
        }
    }
    //比较二维数组中的相同字符
    let maxLen = 0;//用于表示连续相等的子串的长度
    let index = 0;//表示在str1和str2中相同字符的最大索引
    for (let i = 0; i <= len1; i++) {
        for (let j = 0; j <= len2; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0
            } else {
                if (str1[i] == str2[j] && str1[i - 1] == str2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
            }
            if (dp[i][j] > maxLen) {
                maxLen = dp[i][j];
                index = i;
            }
        }
    }

    if (maxLen == 0) {
        return "";
    } else {
        let str = "";
        for (let k = index - maxLen; k < index; k++) {
            str += str1[k];
        }
        return str;
    }
}
console.log(lcs("abbcdccdff", 'dbbffcccaff'))

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

# 题目4

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径? 网格中的障碍物和空位置分别用 1 和 0 来表示。说明：m 和 n 的值均不超过 100。

题目解析 1、在不考虑障碍物的情况下，到达终点有两种情况：从终点上方或终点左方到达。所以就有 F(m,n) 最优子结构为F(m,n-1)+F(m-1,n)。 2、所以状态转移公式 为 F(m,n)=F(m,n-1)+F(m-1,n) 3、考虑边界。所有的F(m*n)的矩阵最后都可以拆分为一行和一列的情况，边界情况可以分为两种。 1行n列F(1,n)和 n行1列 F(n,1)。

方法1 递归(自顶向下)

function getPaths (arr) {
    let dp = (m, n) => {
        // 检查起始或者目标元素是不是1(障碍物)，如果起始或者最后那个格就是1，说明怎么都怎么不到那，
        // 直接返回0
        if (arr[m - 1][n - 1] === 1 || arr[0][0] === 1) {
            return 0
        }
        // 有边界
        if (m < 2 || n < 2) {
            // 第一种边界 1行n列
            if (m < 2) {
                return arr[m - 1].includes(1) ? 0 : 1
            } else {
                // 第二种边界 n行1列
                for (let i = 0; i < m; i++) {
                    if (arr[i][0] === 1) {
                        return 0
                    }
                }
                return 1
            }
        } else {
            // 递归
            return dp(m - 1, n) + dp(m, n - 1)
        }
    }
    return dp(arr.length, arr[0].length)
}
//构造m*n的网格
const arr = [];
for (let i = 0; i < 7; i++) {
    arr[i] = [];
    for (let j = 0; j < 3; j++) {
        arr[i][j] = 0
    }

}
console.log(getPaths(arr))

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

方法2 备忘录算法

function getPaths2 (arr) {
    let dp = (m, n, obj = {}) => {
        // 检查起始或者目标元素是不是1(障碍物)，如果起始或者最后那个格就是1，说明怎么都怎么不到那，
        // 直接返回0
        if (arr[m - 1][n - 1] === 1 || arr[0][0] === 1) {
            return 0
        }
        // 有边界
        if (m < 2 || n < 2) {
            // 第一种边界 1行n列
            if (m < 2) {
                return arr[m - 1].includes(1) ? 0 : 1
            } else {
                // 第二种边界 n行1列
                for (let i = 0; i < m; i++) {
                    if (arr[i][0] === 1) {
                        return 0
                    }
                }
                return 1
            }
        } else {
            if (obj[m + ',' + n]) {
                return obj[m + ',' + n]
            } else {
                const value = dp(m - 1, n) + dp(m, n - 1);
                obj[m + ',' + n] = value;
                return value;
            }
        }
    }
    return dp(arr.length, arr[0].length)
}

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

方法3 动态规划-压缩降维

function getPaths2(arr) {
    var n = arr.length;
    var m = arr[0].length;
    var result = Array(m).fill(0);
    for(var i = 0;i < n;i++){
        for(var j = 0;j < m;j++){
            if(i == 0 && j == 0){
                result[j] = 1;
            }
            if(arr[i][j] == 1){
                result[j] = 0;
            }else if(j > 0){
                result[j] += result[j-1];
            }
        }
    }
    return result[m-1];
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 题目5 背包问题

假如你是一保险箱大盗，打开了一个装满奇珍异宝的保险箱，但是你必须将这些宝贝放入你的一个小背包中。保险箱中的物品规格和价值不同。你希望自己的背包装进的宝贝总价值最大。保险箱中有 5 件物品，它们的尺寸分别是 3、4、7、8、9，而它们的价值分别是 4、5、10、11、13，且背包的容积为 16。

分析

找子问题
对于每一个物品，都有装下和装不下两种选择。装不下时，这时的最大价值是前i-1个物品的价值是一样的。装得下时，但是它价值不一定大于当前相同体积的最优价值。因此子问题中物品数和背包容量都应该做为变量。
确定状态
状态对应的值即为背包容量为 j 时，求前 i 个物品所能达到最大价值，设为 dp[i][j]。初始时，dp[0][j](0<=j<=V) 为 0，没有物品也就没有价值。
确定状态转移方程
dp[i][j] 表示将前 i 件物品装进限重为 j 的背包可以获得的最大价值, 0<=i<=N, 0<=j<=W 那么当 i > 0 时dp[i][j]有两种情况：
- 1.不装入第i件物品，即 dp[i−1][j]；
- 2.装入第i件物品（前提是能装下），即 dp[i−1][j−w[i]] + v[i] (第i（i从1开始）件物品的重量为w[i]，价值为v[i])。

    dp[i][j] = max(dp[i−1][j], dp[i−1][j−w[i]]+v[i]) // j >= w[i]

方案1 动态规划

/**
 * 
 * @param {*} capacity 容量
 * @param {*} size 尺寸
 * @param {*} value 价值
 * @param {*} n 物品数量
 */
function dKnapsack (capacity, size, value, n) {
    let K = []; 
    //构建二维数组
    for (let i = 0; i <= n; i++) { 
         K[i] = []; 
        for (let w = 0; w <= capacity; w++) { 
            if (i == 0 || w == 0) { 
                //边界
                K[i][w] = 0; 
            } else if (size[i - 1] <= w) { //判断第i件物体的体积
                //value[i - 1]第i件物品的价值，size[i - 1]第i将物品的大小
                //和不放入该物品时同样达到该体积的最大价值比较
                K[i][w] = max(value[i - 1] + K[i - 1][w - size[i - 1]], K[i - 1][w]); 
                //状态转移公式
            } else {
                //没有放下第i件物品，最大价值不变
                 K[i][w] = K[i - 1][w]; 
            }
        } 
    }

    return K[n][capacity];
}

const value = [4, 5, 10, 11, 13]; 
const size = [3, 4, 7, 8, 9]; 
const capacity = 16; 
const n = 5; 
console.log(dKnapsack(capacity, size, value, n));

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

方案2 递归

function knapsack(capacity, size, value, n) {
    if (n == 0 || capacity == 0) {
        return 0;       
    }       
    if (size[n - 1] > capacity) {
        return knapsack(capacity, size, value, n - 1);
    } else { 
        //比较装下时和没装下的价值大小         
        return max(value[n - 1] + knapsack(capacity - size[n - 1], size, value, n - 1), knapsack(capacity, size, value, n - 1));       
    }    
}

1
2
3
4
5
6
7
8
9
10
11

# 题目 6

给定一个包含非负数的数组和一个目标整数 k，编写一个函数来判断该数组是否含有连续的子数组，其大小至少为 2，总和为 k 的倍数，即总和为 n*k，其中 n 也是一个整数。

var checkSubarraySum = function(nums, k) {
    const dp=new Array(nums.length+1).fill(0)
    let count=0
    //判断是否有连续的两个0
    for(let i=0;i<nums.length;i++){
        if(nums[i]===0){
            count++
        }else{
            count=0
        }
        if(count>=2){
            return true
        }
    }
    //以i为结束点
    for(let i=0;i<nums.length;i++){
        //以j为起点
        for(let j=0;j<=i;j++){
            //逐个相加除以k看是否整除
            dp[j]=(dp[j]+nums[i])%k
            if(i>j&&dp[j]===0){
                return true
            }
        }
    }
    return false
}

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

# 7、剑指 Offer 47. (礼物的最大价值)[https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/]

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

function maxValue(grid){
    const m=grid.length,n=grid[0].length;
    //1、边界条件
    //第一列的礼物的价值
    for(let i=0;i<m;i++){
        grid[i][0]+grid[i-1][0]
    }
    //第一行的礼物的价值
    for(let j=0;j<n;j++){
        grid[0][j]+grid[j-1][0]
    }
    //2、状态转移公式
    for(let i=1;i<m;i++){
        for(let j=1;i<n;j++){
            //到大[i][j]的前一个位置要么是[i-1][j],要么是[i][j-1];
            grid[i][j]+=Math.max(grid[i-1][j],grid[i][j-1])
        }
    }
    return grid[m-1][n-1]
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 8、139. (单词拆分)[]

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

拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

var wordBreak = function(s, wordDict) {
    //动态规划
    const len=s.length;
    //去重
    const wordDictSet=new Set(wordDict);
    const dp=new Array(len+1).fill(false);
    //dp[n]表示 s.substr(0,n)子串存在wordDict中
    dp[0]=true;
    for(let i=1;i<=len;i++){
        for(let j=0;j<i;j++){
            //dp[j]&&wordDictSet.has(s.substr(j,i-j))表示s的前j个字符存在wordDict中,同时s.substr(j,i-j)是否也存在wordDictSet中
            if(dp[j]&&wordDictSet.has(s.substr(j,i-j))){
                dp[i]=true;
                break;
            }
        }
    }
    return dp[len];
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

参考文档
1、漫画：什么是动态规划? (opens new window) 2、 (opens new window)

← 算法基本思想之分治算法算法基本思想之回溯算法 →