アルゴリズムシリーズの宿泊ホテルの最低日数の問題

暴力解決:

function toTheMin(n,m,arr,res) {
    var valueList = arr,
        budget = n,
        num = m,
        flag = 0;
    for(var i = 0, l = valueList.length; i < l; i++) {
        if(valueList[i] <= budget && (valueList[i + 1] > budget) || (i == l - 1)) {
            flag = 1;
            var min = Math.floor(budget / valueList[i]);
            budget = budget - min * valueList[i];
            if(budget < valueList[0]) {
                var res = min + res;
                return res;
            }else {
                return toTheMin(budget, i+1, valueList.slice(0,i), min+res);
            }
        }
    }
    if(flag == 0) {
        return 0;
    }      
}
var arr = [300, 600, 200];
var list = arr.sort(function(a, b) {
    return a - b;
});
var num = list.length;
toTheMin(1000, num, list, 0);

dp実装

function toTheMin2(n,m,arr) {
    var dp = {0:0};
    for(var i = m; i >= 0; i--){
        for(var j = arr[i]; j <= n; j++){
            if(dp[j-arr[i]] != undefined){
                if(dp[j] == undefined) {
                    dp[j] = dp[j-arr[i]] + 1;
                }else{
                    dp[j] = Math.min(dp[j], dp[j-arr[i]] + 1);
                }
            }
        }
    }
    return dp[n];
}