适用场景
常用来求最优解的问题。与分治法相似，都是通过组合子问题的解来求解原问题，动态规划应用于子问题重叠的情况，即不同的问题具有公共的子问题。
动态规划题目解决步骤
- 刻画一个最优解的特征
- 递归地定义最优解的值
- 计算最优解的值，通常采用自底向上的方法
- 利用计算出的信息构造出最优解
题目
钢条切割问题
钢条切割问题描述
最优解特征
将钢条从左边切下长度为i的一段，只对右边n-i的长度继续切割（递归求解），左边不再切割。
递归定义最优解的值
rn = max(pi + rn-1)
自底向下实现
function cut(price, rod) {
if (rod === 0) return 0;
let r = [0];
for (var i = 1; i <= rod; i++) {
let temp = -1;
for (var left = 1; left <= i; left++) {
let rightPrice = r[i - left];
temp = Math.max(temp, price[left] + rightPrice);
}
r[i] = temp;
}
return r[rod];
}
参考资料
算法导论第3版
