动态规划法--JavaScript实现_formula.js

        动态规划(简称DP)的思想是把一个大的问题进行拆分，细分成一个个小的子问题，且能够从这些小的子问题的解当中推导出原问题的解。

一、性质

      1、最优子结构性：既所拆分的子问题的解是最优解。

      2、无后效性：即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。

      3、子问题重叠性质： 既在求解的过程当中，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的解题效率。

二、典型问题

       斐波那契数列的递推式就是动态规划的一种体现

f(i)=f(i−1)+f(i−2),i>=3

      从递归搜索的角度去思考斐波那契数列

function foi(n)
{
    if(n===1 || n===2){
        return 1;
    }else{
        return foi(n-1)+foi(n-2)
    }
}
console.time('time')  //算法的开始时间
 
let str = ""
for(let i=3;i<=20;i++){
    str += foi(i)+"\t"
}
console.log(str)
console.timeEnd('time') //算法的结束时间

      我们会发现上面的程序在超过50项之后计算速度就会以肉眼可见的速度下降，原因是什么呢，就是因为该程序在计算的过程中遇到了大量的子问题的重叠计算。

解决办法：动态规划

const f = new Array()
function dp(n)
{
    f[1] = 1;f[2] = 1;
    for(let i = 3;i <= n ;i ++)
        f[i] = f[i-1] + f[i-2];
}
console.time('time')  //算法的开始时间
dp(50)
console.timeEnd('time') //算法的结束时间
 
let str = ""
for(let i=3;i<f.length;i++){
    str += f[i]+"\t"
}
console.log(str)

三、动态规划求解的基本步骤

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

          初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态

      1、划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。

      2、确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。

      3、确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。

      4、寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。一般，只要解决问题的阶段、状态和状态转移决策确定了，就可以写出状态转移方程（包括边界条件）

四、示例

      1、爬梯子问题

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

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

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

        示例 1：输入： 2   输出： 2

        解释： 有两种方法可以爬到楼顶。

        a、1 阶 + 1 阶     b、2 阶

        示例 2：输入： 3   输出： 3

        解释： 有三种方法可以爬到楼顶。

        a、1 阶 + 1 阶 + 1 阶    b、1 阶 + 2 阶   c、2 阶 + 1 阶

      走1阶台阶只有一种走法，但是走2阶台阶有两种走法（如示例1），如果n是双数，我们可以凑成m个2级台阶，每个m都有两种走法，如果n是单数，那么可以凑成m个2级台阶加上一个1级台阶，这样就是一个排列组合题目，但是开销比较大。

代码如下：

//爬楼梯问题
function climbStairs(n) {
    if (n === 1 || n === 2) {
        return n;
    }
 
    var ways = [];
    ways[0] = 1;
    ways[1] = 2;
    for(var i=2; i<n; i++){
        ways[i]=ways[i-1] + ways[i-2];
    }
    return ways[n-1];
}
console.log(climbStairs(3));//3

2、最大和的连续子数组

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],

输出: 6

解释: 连续子数组 [4,-1,2,1] 的和最大和为 6。

由于要求的是连续子序列和，因此可以将第i个子序列和作为第i+1个子序列和的求值依据，设子序列和为dp(i)，即dp(i) => dp(i + 1)，这样对于[-2,1,-3,4,-1,2,1,-5,4]

当 i = 0 时

连续子序列是他自己，最大连续子序列和就是 [-2]，设它为 dp(0) = -2

i = 1 时

连续子序列是 [dp(0),1] 或者 [1],这时如果选[dp(0),1]作为dp(1)的话，值-1比[1]要小，因此 i = 1 时的最大连续子序列和选择 [1]

i = 2 时

连续子序列是 [dp(1),-3] 或者 [-3],对比dp(1) + -3 = -2 与 [-3]，选择 -2 作为dp(3)

依次类推,我们最终能找到每一个 i 对应的自己最大连续子序列和,因此，我们从中挑选dp(i)最大的最为返回结果

function maxSubArray(nums) {    
    let dp = new Array(nums.length);
    //初始化数据
    dp[0] = nums[0];
    let ans = nums[0];
 
    for(let i = 1; i < nums.length; i ++){
        //获取以nums[i]结尾的最大值
        dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
        //记录最大值
        if(dp[i] > ans) ans = dp[i];
    }
    return ans;
}
console.log(maxSubArray( [-2,1,-3,4,-1,2,1,-5,4])) 

3、0-1背包问题：

        (1)为什么叫做0/1背包呢？为什么不叫1/2背包，2/3背包？？？

每个物品只有一个，对于每个物品而言，只有两种选择，选或者不选，选它记为1，不选记为0，不能将物品进行分割。这就是这个问题被称为0/1背包问题的原因。

       (2)示例：假设有4个物品，它们的价值(v)和重量(w)如下图：

                

        背包总容量为10，现在要从中选择物品装入背包中，要求物品的重量不能超过背包的容量，并且最后放在背包中物品的总价值最大。

let vs = [0,2,4,3,7]; //物品的体积
    let ws = [0,2,3,5,5]; //物品的重量
    let results = [[]]; //二维数组：存放结果集
    for(let i=0;i<5;i++){
        results[i] = []
    }
    
    function testKnapsack3() {
        let result = ks3(4,10);
        console.log(result);
    }
    function ks3(i,j){
        // 初始化
        for (let m = 0; m <= i; m++){
            results[m][0] = 0;
        }
        for (let m = 0; m <= j; m++){
            results[0][m] = 0;
        }
        // 开始填表
        for (let m = 1; m <= i; m++){
            for (let n = 1; n <= j; n++){
                if (n < ws[m]){
                    // 装不进去
                    results[m][n] = results[m-1][n];
                } else {
                    // 容量足够
                    if (results[m-1][n] > results[m-1][n-ws[m]] + vs[m]){
                        // 不装该珠宝，最优价值更大
                        results[m][n] = results[m-1][n];
                    } else {
                        results[m][n] = results[m-1][n-ws[m]] + vs[m];
                    }
                }
            }
        }
        return results[i][j];
    }
 
testKnapsack3()