最近工作上的一些事有所触动，作为程序员，或者一个打工者，对自己的命运把控程度，是要远低于自我认知的。每一天重复又忙碌的工作，极容易麻痹了人的知觉，等到洪水袭来，才发现自己在冷水之中只能用力挣扎。无论每个人的境遇如何，我一直坚信，想让自己平庸的人生轨迹有所突破，必然要做不平凡的事。所以，我想开启一个长期而困难的计划——深入的学习算法。
本文是这个学习路径的第一篇记录。
动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划保存递归时的结果，因而不会在解决同样的问题时花费时间。
动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解（对有些问题这个要求并不能完全满足，故有时需要引入一定的近似）。简单地说，问题能够分解成子问题来解决。
- 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。
- 无后效性。即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。
- 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。
1.斐波那契数列（leetcode.509）
斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 给定 N，计算 F(N)。
输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1.
示例 2：
输入：3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2.
示例 3：
输入：4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3.var fib = n => {
let dp = []
dp[1] = 1
dp[2] = 1
let i = 3
while (n - i >= 0) {
dp[i] = dp[i - 1] + dp[i - 2]
i++
}
return dp[n]
}如果适用递归方法，子问题可能被重复计算多次。
2.买卖股票的最佳时机（leetcode.121）
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
let minPrice = +Infinity
let max = 0
for (let i = 0; i < prices.length; i++) {
if (minPrice >= prices[i]) {
minPrice = prices[i]
} else {
let profit = prices[i] - minPrice
if (max < profit) max = profit
}
}
return max
}
这道题可以转化为寻找波峰波谷的问题。如果数字不是波谷，就用它减去波谷，保存这个收益，取最大值即可。
3.打家劫舍（leetcode.198）
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2:
输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。/**
* @param {number[]} nums
* @return {number}
*/
var rob = function(nums) {
let dp = []
dp[0] = nums[0]
let max = dp[0]||0
for (let i = 1; i < nums.length; i++) {
dp[i] = Math.max(nums[i] + (dp[i - 2]||0), dp[i - 1])
if (max < dp[i]) max = dp[i]
}
return max
}这是动态规划中的一类问题，选或不选的问题。
4. 区域和检索 - 数组不可变（leetcode.303）
给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。
示例：
给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
说明:
你可以假设数组不可变。
会多次调用 sumRange 方法。/**
* @param {number[]} nums
*/
var NumArray = function(nums) {
this.nums = nums
this.sums = []
this.sums[0] = nums[0]
for (let i = 1; i < nums.length; i++) {
this.sums[i] = this.sums[i - 1] + nums[i]
}
}
/**
* @param {number} i
* @param {number} j
* @return {number}
*/
NumArray.prototype.sumRange = function(i, j) {
return this.sums[j] - this.sums[i] + this.nums[i]
}
/**
* Your NumArray object will be instantiated and called as such:
* var obj = new NumArray(nums)
* var param_1 = obj.sumRange(i,j)
*/将数组每一项作为数组最后一项，求得和的数组。然后将sumRange转化为两端和只差，问题就迎刃而解了。
5. 使用最小花费爬楼梯（leetcode.746）
数组的每个索引做为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 costi。
每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。
您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。
示例 1:
输入: cost = [10, 15, 20]
输出: 15
解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。
示例 2:
输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出: 6
解释: 最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。
注意：
cost 的长度将会在 [2, 1000]。
每一个 cost[i] 将会是一个Integer类型，范围为 [0, 999]。/**
* @param {number[]} cost
* @return {number}
*/
var minCostClimbingStairs = function(cost) {
let dp = []
dp[0] = cost[0]
let min = +Infinity
for (let i = 1; i <= cost.length; i++) {
dp[i] = (cost[i] || 0) + Math.min(dp[i - 2] || 0, dp[i - 1])
}
return dp[cost.length]
}这几道动态规划的题，正是印证了上文提到的适用情况。碰到问题如果能迅速划归到动态规划范畴类，那么思路往往清晰不少。