【JS算法】动态规划 - 斐波那契数列

动态规划算法

动态规划算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法。
其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
与分治法不同，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立。即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解。

力扣509题：斐波那契数列

[0,1,1,2,3,5,8,13...]

输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

直接列出数组，想取谁取谁
var fib = function(n) {
    let dp = [0,1]
    for(let i=2;i<=n; i++){
        dp[i] = dp[i-1]+dp[i-2]
    }
    return dp[n]
};

递归写发

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

第一种方法可以在优化，因为不需要列出数组，只需要有前两值即可

var fib = function(n) {
    if(n<=1){
        return n
    }
    let dp1 = 0
    let dp2 = 1
    let dp3
    for( let i=2; i<=n;i++){
        dp3=dp1+dp2
        dp1 = dp2
        dp2 = dp3
    }
    return dp3
};

322题: 零钱兑换

题目出一个金额，和硬币面值。答：凑成这个金额所需的 最少的硬币个数

答题思路 - 如5元：
假定1-5元的数组为 dp=[5个 Infinity 无穷大]
用金额2 - 1元硬币 = 1，1+减去的1个硬币=2; dp=[1,2]
用金额5 - 1元硬币 = 4，还需4个+减去的1个硬币=5个硬币
用金额3 - 2元硬币 = 1，还需1个+减去的1个硬币=2个
用金额5 - 2元硬币 = 3，3上面算了需要2个，那就是2+1=3个
dp[5-2] + 1=3个

var coinChange = function(coins, amount) {
    if(!amount){
        return 0;
    }
    //初始化dp数组，长度为金额+1，元素全部为无穷大[Infinity,Infinity,Infinity,Infinity...]
    let dp = Array(amount+1).fill(Infinity) 
    dp[0] = 0
    //硬币假设为[1,2,5]
    for(let i=0; i<coins.length;i++){        
        for( let j=coins[i];j<=amount;j++){           
            dp[j] = Math.min(dp[j-coins[i]]+ 1,dp[j])  //取最小
        } 
    }
    return dp[amount]===Infinity?-1:dp[amount]
};