关于javascript:动态规划

乏味的定义

How should I explain dynamic programming to a 4-year-old?
底下有个 42K 同意的答案，是这样说的：
writes down “1+1+1+1+1+1+1+1 =” on a sheet of paper
“What’s that equal to?”
counting “Eight!”
writes down another “1+” on the left
“What about that?”
quickly “Nine!”
“How’d you know it was nine so fast?”
“You just added one more”
“So you didn’t need to recount because you remembered there were eight!Dynamic Programming is just a fancy way to say ‘remembering stuff to save time later'”

斐波那契数列

什么是斐波那契额数列呢？

fb(0) = 1;
fb(1) = 1;
fb(2) = 2;
fb(n) = fb(n-2) + fb(n-1);

和青蛙跳台阶，人爬楼梯问题一样，都是属于斐波那契数列。
那么，如何求一个斐波那契数列呢？

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

那么这段代码有什么问题呢？
<!– 黑板画图 –>
这颗二叉树的的高度是 N01，节点数靠近 2 的 N - 1 次方，工夫复杂度高达 O(2^n);
<!– 演示 –>
https://www.cs.usfca.edu/~gal…

既然会有那么多反复的呈现，能够用一个 map 来存储, 这也叫做备忘录算法，很多状况下还是须要用到的。

function fibout() {let hash = new Map();
    return function(n) {if(hash.has(n)) return hash.get(n);
        if(n < 2) return 1;
        let res = fib(n - 1) + fib(n - 2);
        hash.set(n, res);
        return res;
    }
}
let fib = fibout();

这样来剖析下工夫复杂度 O(2n) => O(n), 空间复杂度 O（n）;
那么这段代码会有什么问题呢？

因为 return 前就进入下一轮函数，所以须要保留以后的栈
爆栈的可能
<!– 演示 –>

那么，咱们看到，之前求的这个是从后往前求的数据，如果从前往后，改用迭代的形式呢？

function fib(n) {let dp = [1,1];
    for(i = 2; i <=n; i++) {dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

斐波那契，就是一个典型的，用于解释动静布局的一个最简略的例子
能够看到，上述的代码的工夫复杂度，最终升高到了真 O(n)的程度，然而空间复杂度也是 O(n)。
那么，还能优化吗？

能够发现，上述的后果集，其实只和后面两个数无关
<!– 画图 –>

所以能够优化为

function fib(n) {
    let pre = 1;
    let cur = 1;
    let next = 0;
    for(i = 2; i <=n; i++) {
        next = pre + cur;
        pre = cur;
        cur = next;
    }
    return next;
}

这样，空间复杂度就升高到了 O(1)的程度。

通过上述例子，能够看出，遇到动静布局的题目，能够找到它的状态转移方程，就是相似上述的dp[i] = dp[i - 1] + dp[i - 2]，就是我不须要感知所有的值，我只须要拿到之前计算好的值来算就能够了。

上面来一个略微简单一点的例子。
说这个例子前，咱们先想一下, 当你在搜寻框中，一不小心输错单词时，搜索引擎会十分智能地检测出你的拼写错误，并且用对应的正确单词来进行搜寻。你是否想过，这个性能是怎么实现的呢？
funf => fund

这个性能，能够变成如何量化两个字符串的类似度？
计算机只意识数字，所以要解答这个问题，咱们就要先来看，如何量化两个字符串之间的类似水平呢？有一个十分驰名的量化办法，那就是编辑间隔（Edit Distance）。

顾名思义，编辑间隔指的就是，将一个字符串转化成另一个字符串，须要的起码编辑操作次数（比方减少一个字符、删除一个字符、替换一个字符）。编辑间隔越大，阐明两个字符串的类似水平越小；相同，编辑间隔就越小，阐明两个字符串的类似水平越大。对于两个完全相同的字符串来说，编辑间隔就是 0。

依据所蕴含的编辑操作品种的不同，编辑间隔有多种不同的计算形式，比拟驰名的有莱文斯坦间隔 （Levenshtein distance） 和最长公共子串长度（Longest common substring length）。其中，莱文斯坦间隔容许减少、删除、替换字符这三个编辑操作，最长公共子串长度只容许减少、删除字符这两个编辑操作。

咱们明天就来看一下，最长公共子串

str1 = educational
str2 = advantage
<!– 画图 –>

那么，能够发现，匹配两个字符串，能够分成三种状况
两个字符位完全一致，
假如 hello 和 tomato, 它们的最初一位都是 o, 那是不是能够合成为
hell 和 tomat 的最长子串加上 o?
这种状况，叫 减而治之
然而更多的状况，是最初两位不等，那么应该咋办呢？
也就是用 str1 – l 后的 str1，去和 str2 匹配或者是 str1 和 str2 减去 e 后的值，进行匹配。
那么这种离开的状况，叫做 分而治之。

那递归式是不是就能写进去了？

function getMaxSubStr(str1, str2) {
    let len1 = str1.length;
    let len2 = str2.length;
    if(!len1 || !len2) return 0;
    let max = 0;
    if(str1[len1 - 1] == str2[len2 - 1]) {max = 1 + getMaxSubStr(str1.substring(0, len1 - 1), str2.substring(0, len2 - 1));
    } else {max = Math.max(getMaxSubStr(str1.substring(0, len1 - 1), str2), getMaxSubStr(str1, str2.substring(0, len2 - 1)))
    }
    return max;
}

这个的问题和斐波那契的问题相似。

那么如何用 dp 革新一下呢？
大家能够想一下

因为咱们这里有两个字符串，所以咱们须要一个二维的 dp 数组来辅助解决问题。

function getMaxSubStr(str1, str2) {
    let m = str1.length;
    let n = str2.length;
    var dp = Array.from(new Array(m + 1), () => new Array(n + 1).fill(0));
    for(var i = 1; i <= m; i++) {for( var j = 1; j <= n; j++) {if(str1[i-1] == str2[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[m][n];
}

如果是要求最长公共子序列的值呢？你们本人想一下

上面，咱们来看一个动静布局的实例
https://leetcode-cn.com/probl…

<!– 画图剖析 –>

function getJobs(startTime, endTime, profit) {var jobs = [];
    for (var i = 0; i < startTime.length; i++) {let arr = [startTime[i], endTime[i], profit[i]];
        jobs.push(arr);
    }
    return jobs.sort(([s1,e1], [s2,e2])=> e1 - e2);
}

function getPres(jobs) {var res = [-1];
    let cur = 1;
    let pre = cur - 1;
    while (cur < jobs.length) {if (pre < 0 || jobs[cur][0] >= jobs

[1]) {

            res[cur] = pre;

            cur++;

            pre = cur - 1;

        } else {

            pre--;

        }

    }

    return res;

}
var jobScheduling = function (startTime, endTime, profit) {

    let jobs = getJobs(startTime, endTime, profit);

    let pres = getPres(jobs);

    var dp = [];

    // 哨兵

    dp[-1] = 0;

    for (var i = 0; i < jobs.length; i++) {

        dp[i] = Math.max(dp[i - 1], jobs[i][2] + dp[pres[i]]);

    }

    return dp[jobs.length - 1];

};


补发 2020 年文章