一、引言

动态规划(Dynamic Programming)，简称DP，是一种常用的算法思想，它的核心思想是将原问题分解成若干个子问题，通过解决子问题的最优解来得到原问题的最优解。动态规划算法通常用于求解具有重叠子问题和最优子结构性质的问题。

动态规划算法一般分为四步：定义状态、确定状态转移方程、确定边界条件、计算最优解。动态规划问题也是面试中常考的一类算法题，这篇文章将通过仔细介绍力扣(LeetCode)上的五道题目来简单入门一下动态规划问题。解法肯定不唯一，大家用自己喜欢的就行。

二、斐波那契数

//数据范围、类型
//0 <= n <= 30
/**
 * @param {number} n
 * @return {number}
 */

// 斐波那契数
var fib = function(n) {
  // 创建一个数组来保存斐波那契数列的前两个元素
  const dp = [0 ,1];
  // 状态转移方程：F(n) = F(n-1) + F(n-2)
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i-1] + dp[i-2];
  }
  // 返回第n个斐波那契数列的值
  return dp[n];
};

斐波那契数真的是入门级的动态规划题目了，状态转移方程直接在题目中给你了，都不用我们自己去找。

三、爬楼梯

//数据范围、类型
//1 <= n <= 45
/**
 * @param {number} n
 * @return {number}
 */

//爬楼梯
var climbStairs = function(n) {
  // 定义一个数组来保存每一层楼梯的不同爬法数
  const dp = new Array(n + 1);
  // 初始状态：第0层和第1层的不同爬法数均为1
  dp[0] = 1;
  dp[1] = 1;
  // 状态转移方程：第i层的不同爬法数等于第i-1层和第i-2层的不同爬法数之和
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  // 最终结果为第n层的不同爬法数
  return dp[n];
};

假设有0级台阶、1阶台阶、2阶台阶。。。n级台阶，所以设置一个长度为(n+1)的数组。如果最终爬到了n级台阶，那么在这之前的一步，根据题意，一定是爬了1或2个台阶才上到了n级台阶的，所以爬到n级台阶的爬法数是爬到(n-1)级台阶爬法数和爬到(n-2)级台阶爬法数的和，这就有点像斐波那契数列的公式一样。

四、使用最小花费爬楼梯

//数据范围、类型
//2 <= cost.length <= 1000
//0 <= cost[i] <= 999
/**
 * @param {number[]} cost
 * @return {number}
 */

//使用最小花费爬楼梯
var minCostClimbingStairs = function(cost) {
  const n = cost.length;
  // 定义一个数组来保存到达每个台阶的最小花费
  const dp = new Array(n);
  // 初始状态：到达第0个和第1个台阶的最小花费均为对应的费用
  dp[0] = cost[0];
  dp[1] = cost[1];
  // 状态转移方程：第i个台阶的最小花费为从第i-1个台阶和第i-2个台阶中选择最小花费加上到达第i个台阶的费用
  for (let i = 2; i < n; i++) {
    dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
  }
  // 比较从第n-1个台阶上楼顶和从第n-2个台阶上楼顶的花费，选较小的那个
  return Math.min(dp[n - 1], dp[n - 2]);
};

n = cost.length，数组长度是n，下标最大是n-1，dp[n]表示到达楼顶所花的最小费用。 dp[0]和dp[1]已经初始化了，所以从下标2开始遍历。

可能是爬一级台阶上到楼顶的，也可能是爬两级台阶上去的，所以求这两种情况的最小值，再加上从那花费更小的一级爬上楼顶的花费。

五、买卖股票的最佳时机

//数据范围、类型
//1 <= prices.length <= 10的5次方
//0 <= prices[i] <= 10的4次方
/**
 * @param {number[]} prices
 * @return {number}
 */

// 买卖股票的最佳时机
function maxProfit(prices) {
  const n = prices.length;
  // 初始化 dp 数组，dp[i] 表示在第 i 天卖出股票所能获得的最大利润
  const dp = new Array(n).fill(0);
  // 设置初始值
  let minPrice = prices[0];
  for (let i = 1; i < n; i++) {
    // 状态转移方程，dp[i - 1] 表示前 i-1 天的最大利润
    // prices[i] - minPrice 表示第 i 天的最大利润
    dp[i] = Math.max(dp[i - 1], prices[i] - minPrice);
    // 更新 minPrice，找到前 i 天中的最低价
    minPrice = Math.min(minPrice, prices[i]);
  }
  // 返回 dp 数组中的最大值，即为最大利润
  return dp[n-1];
}

大致思想是：不断地更新每一天的最大利润和股票的最低价格。因为要不断地赋值，所以fill(0)用0填充数组，方便之后赋值。第i天的最大利润是第(i-1)天之前的最大利润和第i天利润的较大值，由此确定状态转移方程。

六、打家劫舍

//数据范围、类型
//1 <= nums.length <= 100
//0 <= nums[i] <= 400
/**
 * @param {number[]} nums
 * @return {number}
 */

// 打家劫舍
var rob = function(nums) {
  // 创建一个数组来保存偷前i个房子能够获得的最大价值
  const dp = [nums[0]]; // 偷第一个房子的最大价值为第一个房子的价值
  // 如果数组只有一个元素，则返回该元素的值
  if (nums.length === 1) {
    return dp[0];
  }
  // 如果数组有两个元素，则返回其中的最大值
  dp[1] = Math.max(nums[0], nums[1]);
  if (nums.length === 2) {
    return dp[1];
  }
  const n = nums.length;
  // 状态转移方程：dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])
  for (let i = 2; i < n; i++) {
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
  }
  // 返回偷前n个房子能够获得的最大价值
  return dp[n - 1];
};

这里的dp[i]指的是下标i以前的所有房子和下标为i的这个房子的偷窃金额最大值，下标i这个房子可能被偷也可能不偷，表示一段范围、一段区间的偷窃金额最大值。

如果偷了第i间房屋，那么前一间房屋肯定不能偷，因为题目说了“如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警”。那么偷窃金额就是截止到前两间房屋(i-2)的最大金额加上第i间的金额: dp[i - 2] + nums[i]。

如果没偷第i间房屋，那么偷窃金额就是截止到(i-1)间房屋的最大金额：dp[i - 1]。

七、最后的话

能力一般，水平有限，本文可能存在纰漏或错误，如有问题欢迎各位大佬指正，感谢你阅读这篇文章，如果你觉得写得还行的话，不要忘记点赞、评论、收藏哦！祝生活愉快！