js動態規劃找零問題

wangym 發布于2019-08-20 17:14 / 2905人閱讀

摘要：存儲了到的最優解的找零是或者或者或者的最優解個數是最優解是子解的子解是的最優解的最優解的最優解的最優解類推如果剛好找完返回每個最優解存儲起來

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零錢動態規劃

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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