v2-365a2ad2ad74981966c161d92eb9b61d_720w.jpg
如何单独运行js文件：
1.安装node
2.在命令窗口中输入
node demo.js
动态规划解题套路框架
动态规划问题的一般形式就是求最值。
求解动态规划的核心问题是穷举
动态规划的穷举有点特别，因为这类问题存在「重叠子问题」
需要「备忘录」或者「DP table」来优化穷举过程
正确的「状态转移方程」才能正确地穷举。
例子 一：斐波那契数列代码实现
image.png
- 暴力求解
var count = 0;
var N = 20;
// 暴力求解
function fibo(n) {
count++;
if (n == 1 || n == 2) return 1;
return fibo(n - 1) + fibo(n - 2);
}
console.log(fibo(N));
console.log("函数执行次数" + count);
console.log("暴力求解=====================================")
- 带备忘录的递归解法
var count = 0;
var N = 20;
// 备忘录方法
var arry = new Array(N + 1);
for (var i = 0; i <= N + 1; i++) {
arry[i] = 0;
}
function fibo(n) {
count++;
if (n == 1 || n == 2) return 1;
if (arry[n] != 0) return arry[n];
arry[n] = fibo(n - 1) + fibo(n - 2)
return arry[n];
}
console.log(fibo(N));
console.log("函数执行次数" + count);
console.log("备忘录方法=====================================")
- dp 数组的迭代解法
var count = 0;
var N = 20;
// dp数组方法
var dp = new Array(N + 1);
function fibo(n) {
dp[1] = dp[2] = 1;
for (var i = 3; i < N + 1; i++) {
count++;
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
console.log(fibo(N));
console.log("函数执行次数" + count);
console.log("dp数组方法=====================================")
运行次数对比：
image.png
千万不要看不起暴力解，动态规划问题最困难的就是写出状态转移方程，即这个暴力解。优化方法无非是用备忘录或者 DP table，再无奥妙可言。
动态规划最重要的就是能写出状态转移方程，前提也就是你能暴力求解出来。
例子二：凑零钱问题
先看下题目：给你 k 种面值的硬币，面值分别为 c1, c2 ... ck，每种硬币的数量无限，再给一个总金额 amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1 。
比如说 k = 3，面值分别为 1，2，5，总金额 amount = 11。那么最少需要 3 枚硬币凑出，即 11 = 5 + 5 + 1。
- 暴力求解
var coins = [1, 2, 5];
var amount = 11;
var count = 0;
//暴力求解
function dp(n) {
count++;
//判断是否凑整
if (n == 0) return 0;
if (n < 0) return -1;
var res = Number.MAX_VALUE;
for (let index in coins) {
var subproblem = dp(n - coins[index]);
if (subproblem == -1) continue;
res = subproblem + 1 < res ? subproblem + 1 : res;
}
return res;
}
console.log(dp(amount));
console.log(count);
console.log("暴力求解===============================================================");
- 备忘录方法
//备忘录方法
var note = new Array(amount + 1);
for (var i = 0; i <= amount + 1; i++) {
note[i] = 0;
}
function dp(n) {
count++;
if (note[n] != 0) return note[n];
//判断是否凑整
if (n == 0) return 0;
if (n < 0) return -1;
var res = Number.MAX_VALUE;
for (let index in coins) {
var subproblem = dp(n - coins[index]);
if (subproblem == -1) continue;
res = subproblem + 1 < res ? subproblem + 1 : res;
}
note[n] = res;
return res;
}
console.log(dp(amount));
console.log(note);
console.log(count);
console.log("备忘录方法===============================================================");
- dp数组迭代
//dp数组迭代
var coins = [1, 2, 5];
var amount = 11;
var count = 0;
//初始化数组
var dparry = new Array(amount + 1);
for (var i = 0; i <= amount + 1; i++) {
dparry[i] = amount + 1;
}
//base case
dparry[0] = 0;
function dp(amount) {
for (var i = 0; i <= amount + 1; i++) {
for (var j = 0; j < 3; j++) {
if (i - coins[j] < 0) continue;
dparry[i] = Math.min(dparry[i], 1 + dparry[i - coins[j]]);
count++;
}
}
return dparry[amount];
}
console.log(dp(amount));
console.log(count);
console.log("备忘录方法===============================================================")
总结：
- 动态规划一定要符合「最优子结构」，子问题间必须互相独立
总结：
- 计算机解决问题其实没有任何奇技淫巧，它唯一的解决办法就是穷举，穷举所有可能性。算法设计无非就是先思考“如何穷举”，然后再追求“如何聪明地穷举”。
具有重叠子问题才会使用动态规划法。
