js动态规划找零问题

wangym 发布于2019-08-20 17:14 / 2914人阅读

摘要：存储了到的最优解的找零是或者或者或者的最优解个数是最优解是子解的子解是的最优解的最优解的最优解的最优解类推如果刚好找完返回每个最优解存储起来

function MinCoinChange(coins) {
  var coins = coins;
  //  cache存储了1到37的最优解
  //  37的找零 是36 或者32  或者27 或者12 的最优解个数+1
  var cache = {};
  this.makeChange = function(amount) {
    var me = this;
    if (!amount) {
      return [];
    }
    if (cache[amount]) {
      return cache[amount];
    }
    //  min是最优解 newMin是子解 36的子解是(35的最优解 31的最优解 26的最优解 11的最优解)---->类推
    var min = [],
      newMin, newAmount;
    for (var i = 0; i < coins.length; i++) {
      var coin = coins[i];
      newAmount = amount - coin;
      if (newAmount >= 0) {
        //  如果刚好找完 newAmount = 0  返回newMin = [];
        newMin = me.makeChange(newAmount);
      }
      if (newAmount >= 0 && (newMin.length < min.length - 1 || !min.length) && (newMin.length || !newAmount)) {
        min = [coin].concat(newMin);
      } 
    }
    //  每个最优解存储起来
    return (cache[amount] = min);
  }
  this.cache = function() {
    console.log(cache);
  }
}
var a = new MinCoinChange([1, 5, 10, 25]);
console.log(a.makeChange(36));

GPU云服务器云服务器动态规划动态规划python java动态规划代码 java零钱动态规划

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/83424.html

前端笔面试中的编程题

摘要：之前是写在面试记录里的，题目有点开始多了就分割出来专门来一篇了实现一个函数，接受一个参数，输出个递增自然数输出的自然数不能含有，，或为的倍数，如果含有或为的倍数，则输出下一个自然数支持多次调用，从开始，每次自上次调用的末尾自然数继续打印示例之前是写在面试记录里的，题目有点开始多了就分割出来专门来一篇了实现一个函数printNum，接受一个参数n，输出n个递增自然数· 输出的自然...

Karuru 2019-08-26 12:18 评论0 收藏0
JS之数据结构与算法 (5)

摘要：序列文章面试之函数面试之对象面试之数组的几个不操作面试之对比分析前言数据结构是计算机存储组织数据的方式算法是系统描述解决问题的策略。了解基本的数据结构和算法可以提高代码的性能和质量。 showImg(https://segmentfault.com/img/bVbqYZQ?w=3000&h=2250); 序列文章 JS面试之函数(1)JS面试之对象(2)JS面试之数组的几个不low操作...

wangtdgoodluck 2019-08-23 16:48 评论0 收藏0
现金找零方式的总数（sicp）

问题：现有现金a，并且有n种面额的零钱，问，共有多少种找零方式。问题细化：现有现金1元，并且有50分，25分，10分，5分，1分五种面额，用这5种零钱组成1元，共有多少种方式？如果把n种零钱按照某种顺序排列（如50分，25分，10分，5分，1分，不一定升序或降序，也可以乱序），那么问题可以转化为：现金a用除第一种零钱之外其他面额的找零方式数目加上现金a-d用所有面额的找零方式数目，其中d为第一...

pf_miles 2019-08-22 11:23 评论0 收藏0
SICP Python 描述 3.2 函数和所生成的过程

摘要：函数和所生成的过程来源译者飞龙协议函数是计算过程的局部演化模式。在这一章中，我们会检测一些用于简单函数所生成过程的通用模型。也就是说，递归函数的执行过程可能需要再次调用这个函数。 3.2 函数和所生成的过程来源：3.2 Functions and the Processes They Generate 译者：飞龙协议：CC BY-NC-SA 4.0 函数是计算过程的局部演化...

lolomaco 2019-07-25 10:47 评论0 收藏0
比特币入门笔记

摘要：也就是说，比特币是一个完全出于社区共识的货币。所谓全称为，它是比特币交易的基本单位。根据比特币的协议，一个区块的大小是而一笔交易大概是，因此一个区块大概可以包含笔交易。诞生比特币诞生于 2008 年，一个网名为中本聪的人，提出了一个设想：创造一种不受政府或任何组织控制的货币比特币的本质就是一串数字，没有任何资产支持（现行货币背后都是国家或银行提供资产支持）。也就是说，比特币是一...

Loong_T 2019-06-27 18:40 评论0 收藏0