动态规划：
递归是从顶部开始将问题分解，通过解决所有分解出小问题来解决整体问题；
动态规划从底部开始解决问题，将所有小问题解决，然后合并掉一个整体解决方案；
function dynFib(n) {
var val = [];
for(var i = 1; i <= n; ++i) {
val[i] = 1;
}
if(n === 1) {
return 1;
} else {
for(var i = 2; i <= n; ++i) {
val[i] = i * val[i-1];
}
return val[n];
}
}
function iterFib(n) {
var last = 1,
result = 1;
for(var i = 2; i <= n; ++i) {
result = last * i;
last = result;
}
return result;
}
背包问题：
- 递归解决：
function max(a,b) {
return (a > b) ? a : b;
}
function knapsack(capacity,size,value,n) {
if(n == 0 || capacity ==0) {
return 0;
}
if(size[n -1] > capacity) {
return knapsack(capacity,size,value,n-1);
} else {
return max(value[n - 1] +
knapsack(capacity - size[n - 1],size,value,n-1),
knapsack(capacity,size,value,n-1));
}
}
var value = [4,5,10,11,13],
size = [3,4,7,8,9],
capacity = 16,
n = 5;
console.log(knapsack(capacity,size,value,n));
- 动态规划：
function max(a,b) {
return (a > b) ? a : b;
}
function dknapsack(capacity,size,value,n) {
var k = [];
for(var i = 0; i <= capacity + 1; ++i) {
k[i] = [];
}
for(var i = 0; i <= n; ++i) {
for(var w = 0; w <= capacity; ++w) {
if(i == 0 || w == 0) {
k[i][w] = 0;
} else if(size[i - 1] <= w) {
k[i][w] = max(value[i - 1] + k[i - 1][w - size[i - 1]], k[i - 1][w]);
} else {
k[i][w] = k[i - 1][w];
}
}
}
return k[n][capacity];
}
var value = [4,5,10,11,13],
size = [3,4,7,8,9],
capacity = 16,
n = 5;
console.log(dknapsack(capacity,size,value,n));