两道算法题，彻底弄懂动态规划

动态规划

• 动态规划是算法设计中的一种方法。
• 它将一个问题分解为相互重叠的子问题， 通过反复求解子问题来解决原来的问题。

斐波纳契数列就是经典的动态规划问题

1， 1， 2， 3， 5,  8， 13 ...
复制代码

抽象成表达式， n >= 2, 第 n 个数等于 始终有F(n) = F(n – 1) + F(n – 2)

• 定义子问题

  F(n) = F(n - 1) + F(n - 2)
  复制代码

• 反复执行子问题

    从2循环到n, 执行子问题
  复制代码

通过两道LeetCode算法题，来了解一下吧

1. LeetCode 70. 爬楼梯

1. 题目描述：

   假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
   每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
   注意：给定 n 是一个正整数。
   复制代码

2. 解题思路

• 爬到第n阶可以在第 n-1 阶 爬一个台阶， 或者 在第 n-2 阶 爬两个台阶
• F(n) = F(n – 1) + F(n – 2)

例如n=3时，爬到第3阶的方法 就等于 爬到第2阶的方法 加上 爬到第一阶的方法，即 2 + 1
复制代码

3. 使用动态规划

• 解法一：

var climbStairs = function(n) {
   if (n < 2) return 1
   // 这里设计db的下标 刚好 与第几阶 对应，这样取第n阶的方法就是 db[n]
   let db = [1, 1, 2] // 下标为2，就是需要2步 
   for (let i = 2; i <= n; i ++) {
       db[i] = db[i - 1] + db[i - 2]
   }
   return db[n] // db --> [1, 1, 2, 3, 5]
};


时间复杂度： O(n)
空间复杂度： O(n)

复制代码

• 解法二进阶版：

var climbStairs = function(n) {
   if (n < 2) return 1
   let dp0 = 1; // 用来表示第0阶的方法
   let dp1 = 1; // 用来表示第1阶的方法
   for (let i = 2; i <= n; i ++) {
       const temp = dp0
       dp0 = dp1 // 不断的让dp0代表倒数第二个数字
       dp1 = dp1 + temp 不断的让dp1代表倒数的第一个数字，倒数第一个数字等于前两位之和
   }
   return dp1
};
时间复杂度： O(n)
空间复杂度： O(1)

复制代码

2.LeetCode 198.打家劫舍

1. 题目描述:

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，
影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，
计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

通俗一点就是：不能连续偷相邻的房间
复制代码

—

示例一：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例二：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。
复制代码

2. 解题思路

 - F(k) = 从前 k 个房屋中能偷窃盗的最大数额
 - A(k) = 第 k 个房屋的钱数
 - F(k) = max( F(k - 2) + A(k), F(k - 1) )
复制代码

输入： [1， 2， 3，1]
输出：4

1. k = 1, 只有一个房间， 最大金额就是F(1) = 1
2. k = 2, 有两个房间，最大金额就是 Math.max( F(1), F(2) )
3. k = 3, 有三个房间，最大金额就是 Math.max( F(1) + F(3), F(2) )
4. k = 4, 有四个房间，最大金额就是 前两个房间金额的最大值，加上第四个， 
                               与 前三个房屋金额的最大值 做比较， 取较大的值
                               即Math.max( F(2) + A(4), F(3) ) 

可以得出 F(k)的公式
F(k) = max( F(k - 2) + A(k), F(k - 1) )
复制代码

• 解法一：

var rob = function(nums) {
   const length = nums.length
   if (length === 0) return 0
   // 这里设计dp的下标 表示 第几个房屋
   // 下标为0，就是前0个房屋打劫到的最大金额为0；下标为1，就是前1个房屋打劫到的最大金额为nums[0]
   const dp = [0, nums[0]] 
   for (let i = 2; i <= length; i ++) {
   //子问题的通项公式：F(k) = max( F(k - 2) + A(k), F(k - 1) )
       dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1])
   }
   return dp[length]
};

时间复杂度：O(n)
空间复杂度：O(n)

复制代码

• 解法二进阶版：

var rob = function(nums) {
   const length = nums.length
   if (length === 0) return 0
   let dp0 = 0
   let dp1 = nums[0] // 前一个房屋能打劫到的最大金额
   for (let i = 2; i <= length; i ++) {
       const dp2 = Math.max( dp0 + nums[i - 1], dp1 )
       dp0 = dp1 
       dp1 = dp2
   }
   return dp1
};

时间复杂度： O(n)
空间复杂度： O(1)
复制代码

总结：

 动态规划是通过反复求解子问题来解决原来的问题，即F(n)的通项公式，
 再把一些特殊情况处理一下即可，如：n = 0, n = 1时。
复制代码