美文网首页
labuladong的算法小抄的javascript实现-动态规

labuladong的算法小抄的javascript实现-动态规

作者: flutter开发精选 | 来源:发表于2020-12-30 17:26 被阅读0次

    文章直达地址: https://labuladong.gitee.io/algo/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%B3%BB%E5%88%97/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E8%AF%A6%E8%A7%A3%E8%BF%9B%E9%98%B6.html

    本系列为labuladong的算法小抄的javascript实现版本,实现原理参考labuladong的算法小抄。
    本文为第0章第2小节《动态规划》所涉及的代码,直接上代码

    //斐波那契数列
    /**
     * @param {number} n
     * @return {number}
     */
    // var fib = function (n) {
    //   if (n < 1) return 0;
    //   const mp = {};
    //   return helper(n, mp);
    // };
    
    // var helper = function (n, mp) {
    //   if (n == 1 || n == 2) return 1;
    //   if (mp[n] != undefined) {
    //     return mp[n];
    //   }
    //   mp[n] = helper(n - 1, mp) + helper(n - 2, mp);
    //   return mp[n];
    // };
    
    var fib = function (n) {
      if (n < 1) return 0;
      if (n == 2 || n == 1) return 1;
      let prev = 1;
      let curr = 1;
      for (let i = 2; i < n; i++) {
        let sum = prev + curr;
        prev = curr;
        curr = sum;
      }
      return curr;
    };
    
    // console.log(fib(3));
    
    /**
     * 凑零钱问题v1.0 暴力穷举
     * @param {number[]} coins
     * @param {number} amount
     * @return {number}
     */
    var coinChange = function (coins, amount) {
      function dp(n) {
        if (n == 0) return 0;
        if (n < 0) return -1;
        let res = Infinity;
        for (let index in coins) {
          let sb = dp(n - coins[index]);
          if (sb == -1) continue;
          res = Math.min(res, 1 + sb);
        }
        return res;
      }
      let num = dp(amount);
      return num == Infinity ? -1 : num;
    };
    
    // /**
    //  * 凑零钱问题v2.0 备忘录
    //  * @param {number[]} coins
    //  * @param {number} amount
    //  * @return {number}
    //  */
    // var coinChange = function (coins, amount) {
    //   let mp = {};
    //   function dp(n) {
    //     if (mp[n]) return mp[n];
    //     if (n == 0) return 0;
    //     if (n < 0) return -1;
    //     let res = Infinity;
    //     for (let index in coins) {
    //       let sb = dp(n - coins[index]);
    //       if (sb == -1) continue;
    //       res = Math.min(res, 1 + sb);
    //     }
    //     if (res != Infinity) {
    //       mp[n] = res;
    //     } else {
    //       mp[n] = -1;
    //     }
    //     return res;
    //   }
    //   let num = dp(amount);
    //   return num == Infinity ? -1 : num;
    // };
    
    /**
     * 凑零钱问题v2.0 备忘录
     * @param {number[]} coins
     * @param {number} amount
     * @return {number}
     */
    var coinChange = function (coins, amount) {
      let infos = new Array(amount + 1);
      infos.fill(amount + 1);
      infos[0] = 0;
      for (let i = 0; i < infos.length; i++) {
        for (let index in coins) {
          if (i - coins[index] < 0) continue;
          infos[i] = Math.min(infos[i], 1 + infos[i - coins[index]]);
        }
      }
      return infos[amount] == amount + 1 ? -1 : infos[amount];
    };
    
    console.log(coinChange([1, 2, 5], 11));
    
    

    相关文章

      网友评论

          本文标题:labuladong的算法小抄的javascript实现-动态规

          本文链接:https://www.haomeiwen.com/subject/aowhoktx.html