动态规划专题

为什么写这篇博客

哈哈，那是因为今天下午笔试题第一题就是最基本的动态规划（最简单那档），虽然我看出来了这是道动态规划，但是我没写出来（其实也有一部分原因是我写前面的逻辑题太慢了，然后后面要写两份岗位的笔试）。
真的很苦露西啊！一出面试的地方脸都直接变了。复杂的心情描写就不写了，真的很难受，当场就觉得自己算法能力有多么差了。
所以决定好好学习动态规划了。

让我心如死灰的那道题

这里只做简单描述：

• 有一排柜子，你可以看到柜子里的糖果数量，你可以打开其中的柜子，但是打开后，这个被打开的柜子旁边的柜子都不能打开了，设计一个方案以拿到最多的糖果
  一眼撇过去就知道是动态规划，当然这里容易混淆的就是贪心。为什么不是贪心呢？因为贪心往往只能找到局部最优解，而无法看到全局最优解。而动态规划就是将大问题细分为小问题，小问题再细分下去，最后小问题解决了归上去给大问题得出解，所以能够找到全局最优解。
  问题是我看得出来，但是没办法构造dp数组，结果就是做不出来（悲)
  现在重新梳理题目，尝试自己想出来思路：
  假设i代表当前第几个柜子，dp[i]代表前第i个柜子能拿到的最多的糖果数量。那么大问题就是到最后一个柜子时，我们能够拿到的最多的糖果数量。
  显而易见，小问题就是前一个柜子能拿到的最多的糖果数量，以此类推。那么最小的问题就是：第一个柜子时能拿到的最多的糖果数量，很明显这个问题的答案时dp[0] = candies[0]。
  得到了最小问题的解，归上去（就像递归不是吗？），第二小的问题就是：前两个柜子能拿到的最多的糖果数量dp[1]是多少。这也很好推了，因为我们要么拿第一个柜子的糖果，要么拿第二个柜子的糖果，所以选更多糖果的那个柜子就好了。
  接下来就是第三小的问题了，dp[2]怎么求呢？其实也很简单。仔细读题，一个柜子被打开后，这个被打开的柜子旁边的柜子都不能打开了，也就是说，要么这个柜子的前一个柜子被打开了，那我们就无法取得当前柜子里的糖果了，而此时可以知道dp[2] = dp[1]；要么前一个柜子没打开，那为了拿到更多的糖果，我们肯定选择打开当前柜子，也就是有dp[2] = dp[0] + candies[2]。
  当然我们要选出最多糖果数量的那种情况，所以有：dp[2] = max(dp[1], dp[0] + candies[2])。所以，我们能够得到公式：dp[i] = max(dp[i - 1], dp[i - 2] + candies[i])。
  可能有人会觉得，你选了当前柜子你不用考虑后面那个柜子不能选的情况吗？当然不需要了，动态规划主打的就是一个每次找到的都是当前情况的全局最优解，如果当前的柜子是最后一个柜子，你难道还会考虑它后面的“柜子”吗？

  public class CandyCabinet {
      public static int openCabinets(int[] candies) {
          int numCabinets = candies.length;
          if (numCabinets == 0) {
              return 0;
          }
          if (numCabinets == 1) {
              return candies[0];
          }
  
          int[] dp = new int[numCabinets];
          dp[0] = candies[0];
          dp[1] = Math.max(candies[0], candies[1]);
  
          for (int i = 2; i < numCabinets; i++) {
              dp[i] = Math.max(dp[i - 1], dp[i - 2] + candies[i]);
          }
  
          return dp[numCabinets - 1];
      }
  
      public static void main(String[] args) {
          int[] candies = {1, 4, 5, 4, 1};  // 柜子中的糖果数量
          int maxCandies = openCabinets(candies);
          System.out.println("最多的糖果数量: " + maxCandies);
      }
  }

  顺便给出python版本的解：

  def open_cabinets(candies):
      num_cabinets = len(candies)
      if num_cabinets == 0:
          return 0
      if num_cabinets == 1:
          return candies[0]
  
      # 使用动态规划记录每个柜子的最优解
      dp = [0] * num_cabinets
      dp[0] = candies[0]
      dp[1] = max(candies[0], candies[1])
  
      for i in range(2, num_cabinets):
          dp[i] = max(dp[i - 1], dp[i - 2] + candies[i])
  
      return dp[-1]

其他的动态规划

70. 爬楼梯

很经典的一题，你一次可以上一阶或者两阶楼梯，你有多少种方法爬n阶楼梯。
那么对于i，表示当前为i阶楼梯，所以dp[i]表示爬i阶楼梯共有几种方法。可以知道dp[0] = 1，dp[1] = 1，dp[2] = 2，而dp[2] = dp[0] + dp[1]，即dp[i] = dp[i - 2] + dp[i - 1]。

public class Solution {
    public int ClimbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        int[] dp = new int[n];
        dp[0] = 1;
        dp[1] = 2;
        for(int i = 2; i < n; i++)
        {
            dp[i] = dp[i - 2] + dp[i - 1];
        }
        return dp[n - 1];
    }
}

看了下题解，发现还可以使用滚动数组优化：

public class Solution {
    public int ClimbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 0; i < n; i++)
        {
            p = q;
            q = r; 
            r = p + q;
        }
        return r;
    }
}

题解上还说了这题如果n太大的话就需要使用矩阵快速幂了，当然我这种数学渣渣看的不是很明白，估计之后有空再去了解。

509. 斐波那契数

这题没什么好说的吧，公式都给了，直接转换成代码。

public class Solution {
    public int Fib(int n) {
        int p = 0, q = 1, r = 1;
        for (int i = 0; i < n; i++)
        {
            p = q; q = r; r = p + q;
        }
        return p;
    }
}

746. 使用最小花费爬楼梯

这题和拿最多糖果那题十分相似，但又有些许不同。对于我们所处的一阶楼梯，我们需要支付当前楼梯的费用，然后选择往上一阶还是两阶，所以要清楚，这里的楼梯顶部并不是cost.Length，而是cost.Length + 1。
比如第一个例子中，cost[2] = 20，此时我们所处位置仍然不算楼梯顶部，真正的楼梯顶部是“cost[3]”，这在之后我们的得到最终问题的答案时要注意。
既然清楚了题目的意思，就尝试把dp[i]写出来吧！在这里，dp[i]代表当我们处于第i个楼梯上时，我们需要的最少费用，所以我们到达这个楼梯时，其实并不需要支付当前楼梯的费用的，只有我们要从这个楼梯往上爬时，才需要加上当前楼梯的费用。
所以得到：dp[0] = dp[1] = 0，我们能够选择从下标为0或者1的楼梯往上爬。对于dp[2]，很容易推出：dp[2] = min(dp[0] + cost[0], dp[1] + cost[1])，因为要到达下标为2的楼梯，有两种方法，走一步和走两步，分别支付之前所在楼梯的费用，再从中取最小值即可。
所以推导公式就出来了：dp[i] = min(dp[i - 2] + cost[i - 2], dp[i - 1]+ cost[i - 1])。

public class Solution {
    public int MinCostClimbingStairs(int[] cost) {
        int n = cost.Length;
        if (n == 2) return Math.Min(cost[0], cost[1]);
        int[] dp = new int[n + 1];
        dp[0] = dp[1] = 0;
        for (int i = 2; i <= n; i++)
        {
            dp[i] = Math.Min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);
        }
        return dp[n];
    }
}

---

希望本文章能够帮到您~