1.应用动态规划求解问题的特点
（1）问题是求最优解
（2） 整体问题的最优解依赖于各个子问题的最优解
（3）大问题分解成若干小问题，这些小问题之间还有相互重叠的更小的子问题
（4） 从上往下分析问题，从下往上求解问题
参考链接：blog.csdn.net/qq_32651225…
2.硬币找零问题（问有多少种方法）
给定数组arr，arr中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数aim代表要找的钱数，求换钱有多少种方法。
解法一：
用f(n)代表要找的钱数为n时，换钱的方法数。用数组arr代表拥有的硬币种类。则f(aim)=f(aim-arr[0])+f(aim-arr[1])+...+f(aim-arr[n])，同理可以推出f(aim-arr[0])=f(aim-arr[0]-arr[0])+f(aim-arr[0]-arr[1])+...f(aim-arr[0]-arr[n]).
var solutions = function (arr, aim) {
return process(arr, 0, aim);
function process(array, index, total) {
var result = 0;
//当array.length==index时，即完成遍历所有硬币种类，若此时total刚好为0，
//则是一种可行的还钱方法，否则不是
if (array.length == index) {
return total == 0 ? 1 : 0;
}
for (var i = 0; array[index] * i <= total; i++) {
var p = process(array, index + 1, total - array[index] * i);
result = result + p;
}
return result;
}
}
上述process(arr,0,aim)方法即f(aim)。process方法计算arr[0]至arr[n]的硬币种类，每种硬币从0至i,且arr[n]*1<total的方法数。内层for循环用来记录arr[index]的硬币数量，递归调用遍历arr代表的硬币种类。
解法二：
声明一个二维数组result[m][n]，result[m][n]表示使用硬币数组0-m时组成总钱数n的方法数。那么使用硬币result[m][n] = result[m-1][n]+result[m-1][n-1*arr[m]]+result[m-1][n-2*arr[m]]+...+result[m-1][n-i*arr[m]] (其中n-i*arr[m]>0)
var solutionsTwo = function (arr, aim) {
var temp = new Array();
//声明一个二维数组temp[arr.length][aim+1]
//aim+1是为了记录边界情况，即aim=0时，找零方法只有一种，就是各种硬币数量均为0
for (var i = 0; i < arr.length; i++) {
temp.push(new Array(aim + 1));
temp[i][0] = 1;
}
//记录只使用一种硬币arr[0]时，组成金额1至aim的情况
for (var n = 1; n < aim + 1; n++) {
if (n % arr[0] == 0) {
temp[0][n] = 1;
} else {
temp[0][n] = 0;
}
}
for (var j = 1; j < temp.length; j++) {
for (var k = 1; k < aim + 1; k++) {
process(arr, j, k);
}
}
function process(array, index, total) {
var result = 0;
for (var o = 0; o * array[index] <= total; o++) {
result = result + temp[index - 1][total - o * array[index]]
}
temp[index][total] = result;
return result;
}
return temp[arr.length - 1][aim];
}
3.最长、最短、最多、最少问题
假设有几种硬币，如1、3、5，并且数量无限。请找出能够组成某个数目的找零所使用最少的硬币数。
用数组arr代表硬币组成的数组，声明一个数组result[n],result[n]表示钱数为n时，找零所使用的最少硬币数。则result[n]= min(result[n-arr[0]+1,result[n-arr[1]+1,...result[n-arr[arr.length-1]+1).
var coinChange = function (coins, amount) {
var tempArr = new Array(amount + 1);
tempArr[0] = 0;
for (let i = 1; i < tempArr.length; i++) {
for (let j = 0; j < coins.length; j++) {
tempArr[i] = lower(tempArr[i], tempArr[i - coins[j]] + 1);
}
}
function lower(x, y) {
if (typeof x == 'undefined' || typeof y == 'undefined') {
return x || y;
}
return x > y ? y : x;
}
return tempArr[amount];
}
给定字符串string1和string2，求最长公共子序列。
var longestString = function (str1, str2) {
var result = [];
var longest = 0;
for (var n = 0; n < str1.length; n++) {
result.push(new Array(str2.length));
if (str1[n] == str2[0]) {
result[n][0] = 1;
} else {
result[n][0] = 0;
}
}
for (var m = 0; m < str2.length; m++) {
if (str2[m] == str1[0]) {
result[0][m] = 1;
} else {
result[0][m] = 0;
}
}
for (var i = 1; i < str1.length; i++) {
for (var j = 1; j < str2.length; j++) {
if (str1[i] == str2[j]) {
result[i][j] = result[i - 1][j - 1] + 1;
longest = Math.max(result[i][j], longest);
}else{
result[i][j] = 0;
}
}
}
return longest;
}
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最多金额。
var rob = function (nums) {
if (nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
var tempArr = new Array();
tempArr = [nums[0], nums[1]];
for (let i = 2; i < nums.length; i++) {
for (let j = i - 2; j >= 0; j--) {
tempArr[i] = higher(tempArr[j] + nums[i], tempArr[i]);
}
}
function higher(x, y) {
if (typeof y == 'undefined') {
return x;
} else if (typeof x == 'undefined') {
return y;
} else {
return x > y ? x : y;
}
}
return Math.max(...tempArr);
};
4.背包问题
给定n个重量为w1，w2 ,w3 ,…,wn ，价值为v1 ,v2 ,v3 ,…,vn 的物品和容量为C的背包，求这个物品中一个最有价值的子集，使得在满足背包的容量的前提下，包内的总价值最大。
声明一个二维数组result[m][n],result[m][n]表示使用0-m个物品，在容量为n时，包内的最大价值。则result[m][n]=Math.max(result[m-1][n],result[m-1][n-1*weight[m]]+1*value[m],result[m-1][n-2*weight[m]]+2*value[m]...)
var bag = function (weight, value, count) {
var result = [];
for (var i = 0; i < weight.length; i++) {
result.push(new Array(count + 1));
result[i][0] = 0;
}
//确定边界情况，只使用weight[0]时的最大价值
for (var j = 1; j < count + 1; j++) {
var k = 0;
while (k * weight[0] <= j) {
k++;
}
result[0][j] = (k - 1) * value[0];
}
for (var m = 1; m < weight.length; m++) {
for (var n = 1; n < count + 1; n++) {
process(m, n);
}
}
function process(m, n) {
var num = 0;
for (var o = 0; o * weight[m] <= n; o++) {
num = higher(num, result[m - 1][n - o * weight[m]] + o * value[m]);
}
result[m][n] = num;
return num;
function higher(x, y) {
if (typeof x == 'undefined' || typeof y == 'undefined') {
return x || y;
}
return x > y ? x : y;
}
}
return result[weight.length - 1][count];
}
