昨天接触了一点动态规划,发现这东西就是知识盲区。所以今天学习动态规划。

参考资料:

**不要迷信 DP!**很多时候,动态规划其实是一种带缓存优化的暴力计算。所以未必能得到最优解。

阶段目标

  • 入门 + 单序列型 DP
  • 双序列型 DP
  • 矩阵坐标型 DP
  • 背包型 DP
  • 区间及其它类型 DP

优化问题和计数问题

优化问题通常要在许多可行解里面找出一个「最好的答案」

计数问题所求的,并非是最好的答案,反而要全面性的计算有几种可能的答案或其加权总数

寻找递归式

优化

入门 + 单序列型 DP

LC 746 使用最小花费爬楼梯

【例子】746. 使用最小花费爬楼梯

一个楼梯,你每次可以前进一步或两步,到达每个位置的代价是 cost [i]。初始位置可以在 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 。

在学习之前,我的解法:

核心思想是:$ 总开销 = 当前步骤开销 + 下一步开销 $,而下一步开销可以递归暴算。不使用缓存会超时,所以加了缓存,减少暴算次数。

class Solution {
public:
  int calc(vector<int> &cache, vector<int> &cost, int cur = -1) {
    // 读缓存
    if (cache[cur] != 0) {
      return cache[cur];
    }
    int end = cost.size() - 1;
    int curcost = cost[cur], nextcost = 0;
    if (cur <= end - 2) {
      int next1c = calc(cache, cost, cur + 1);
      int next2c = calc(cache, cost, cur + 2);
      nextcost = min(next1c, next2c);
    }
    // 总开销 = 当前步骤开销 + 下一步开销
    auto total = curcost + nextcost;
    // 写缓存
    cache[cur] = total;
    return total;
  }
  // 规定:到达之后才计算开销
  int minCostClimbingStairs(vector<int> &cost) {
    // 缓存
    vector<int> cache(cost.size());
    int cur = -1;
    int next1c = INT_MAX, next2c = INT_MAX;
    next1c = calc(cache, cost, cur + 1);
    next2c = calc(cache, cost, cur + 2);
    return min(next1c, next2c);
  }
};

分析

类型:这道题属于单序列型。

递归:$f (i) = \min (f (i - 1),f (i-2)) + \operatorname {cost}[i]$ 表示从 0i 的最小开销。

初始格局:$f (0) = \operatorname {cost}[0]$ $f (1) = \operatorname {cost}[1]$

将其直接表达为递归代码:

class Solution {
public:
  int rec(std::vector<int> &cost, int i) {
    if (i == 0 || i == 1)
      return cost[i];
    return min(rec(cost, i - 1), rec(cost, i - 2)) + cost[i];
  }
  int minCostClimbingStairs(vector<int> &cost) {
    int n = cost.size();
    return min(rec(cost, n - 1), rec(cost, n - 2));
  }
};

时间复杂度:$O (2^n)$

对 T (n) 需要进行 T (n-2), T (n-1) 的递归计算,即每次产生 2 个分支。计算次数为 n,所以一共 $2^n$ 个分支。

对其进行记忆优化(Memorization)

class Solution {
public:
  int rec(std::vector<int> &cost, std::vector<int> &dp, int i) {
    if (i == 0 || i == 1)
      return cost[i];
    if (dp[i] != -1)
      return dp[i];
    dp[i] = min(rec(cost, dp, i - 1), rec(cost, dp, i - 2)) + cost[i];
    return dp[i];
  }
  int minCostClimbingStairs(vector<int> &cost) {
    int n = cost.size();
    std::vector<int> dp(n);
    fill(dp.begin(), dp.end(), -1);
    return min(rec(cost, dp, n - 1), rec(cost, dp, n - 2));
  }
};

从而将其时间复杂度降低到了 $O (n)$ (因为每个 $f (i)$ 只需要计算一次)

对其进行自下而上(Bottom Up)优化

class Solution {
public:
  int minCostClimbingStairs(vector<int> &cost) {
    int n = cost.size();
    std::vector<int> dp(n) = {cost[0] cost[1]};
    for (int i = 2; i < n; i++) {
      dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
    }
    return min(dp[n - 2], dp[n - 1]);
  }
};

先计算最小情形,然后慢慢扩大到目标情形。时间复杂度 $O (n)$,空间复杂度 $O (n)$(DP 数组长度)。

如何继续优化空间复杂度?

可以看到对任意 $i$,引用的只有 $i-1,i-2$,因此没有必要使用 $n$ 大小的数组。只需要用固定大小的内存:

class Solution {
public:
  int minCostClimbingStairs(vector<int> &cost) {
    int n = cost.size();
    vector<int> dp(n);
    int pprev = cost[0];
    int prev = cost[1];
    for (int i = 2; i < n; i++) {
      auto cur = min(prev, pprev) + cost[i];
      pprev = prev;
      prev = cur;
    }
    return min(prev, pprev);
  }
};

这种变量值平移的方式比较不灵活,如果我们要增加依赖(比如 $f (i)$ 依赖 $f (i-1), f (i-2), f (i-3),\cdots$),则又要增加临时变量。解决方法是取模:

class Solution {
public:
  int minCostClimbingStairs(vector<int> &cost) {
    int n = cost.size();
    std::vector<int> dp = {cost[0] cost[1]};
    int d = 2; // 依赖的状态数
    for (int i = 2; i < n; i++) {
      // 比如 i = 2, d = 2,则相当于 dp [0] = min (dp [1], dp [0])
      dp[i % d] = min(dp[(i - 1) % d], dp[(i - 2) % d]) + cost[i];
    }
    return min(dp[0], dp[1]);
  }
};

LC 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 。

分析:

设 $f (i)$ 表示目标函数:盗窃总额。$v [i]$ 表示房屋 $i$ 中的金额。

递推关系:$f (i) = \max (f (i-2), f (i-3),f (i-4), \cdots,f (0)) + v [i]$

初始格局:$f (0) = v [0],f (1) = v [1],f (2)=\max (f (0)) + v [2]$

如果我们自上而下计算,则一开始就涉及到 $[0, i-2]$ 的值。所以不如自下而上计算。根据递推关系:

class Solution {
public:
  int rob(vector<int> &v) {
    if (v.size() == 1) {
      return v[0];
    }
    std::vector<int> dp(v.size());
    dp[0] = v[0];
    dp[1] = v[1];
    int dp_max = 0; // 从 0 到 i-2 的最大值
    for (size_t i = 2; i < v.size(); i++) {
      dp_max = INT_MIN;
      for (int j = 0; j <= i - 2; j++) {
        dp_max = max(dp_max, dp[j]);
      }
      dp[i] = dp_max + v[i];
    }
    print_vec(dp);
    return max(dp[v.size() - 1], dp[v.size() - 2]);
  }
};

下面进行时间优化。

这里我们每次 dp_max 都是从头计算,显然有优化空间。dp_max 表示 f 从 0 到 i-2 的最大值,则当 $i > 2$ 时,只需要让 dp_max = max (dp_max, dp [i - 2])

class Solution {
public:
  int rob(vector<int> &v) {
    if (v.size() == 1) {
      return v[0];
    }
    std::vector<int> dp(v.size());
    dp[0] = v[0];
    dp[1] = v[1];
    int dp_max = 0; // 从 0 到 i-2 的最大值
    for (size_t i = 2; i < v.size(); i++) {
      dp_max = max(dp_max, dp[i - 2]);
      dp[i] = dp_max + v[i];
    }
    return max(dp[v.size() - 1], dp[v.size() - 2]);
  }
};

下面进行时间优化。考虑计算 dp [i] 时,需要依赖 dp [i - 2],两个空间足矣(当然更多也行):

class Solution {
public:
  int rob(vector<int> &v) {
    if (v.size() == 1) {
      return v[0];
    }
    int d = 2; //d >= 2 都行
    std::vector<int> dp(d);
    dp[0] = v[0];
    dp[1] = v[1];
    int dp_max = 0; // 从 0 到 i-2 的最大值
    for (size_t i = 2; i < v.size(); i++) {
      dp_max = max(dp_max, dp[(i - 2) % d]);
      dp[i % d] = dp_max + v[i];
    }
    return max(dp[(v.size() - 1) % d], dp[(v.size() - 2) % d]);
  }
};

另一种解法:

我们定义 $f (i) = \max (f (i-2) + v [i],f (i-1))$

则自下而上解法:

int rob(vector<int> v){
    int n = v.size();
    if(n == 1) return v[0];
    vector<int> dp = {v[0], max(v[0], v[1])};
    for (int i = 2; i < n; i++){
        dp[i % 2] = max(dp[(i - 1) % 2], dp[(i - 2) % 2] + v[i]);
	}
    return dp[(n - 1) % 2];
}

LC 213 打家劫舍 II (环形数组)

这道题和上一题一样,除了这题的房子围成一圈。

分析:

Case 1:相当于抹掉最后一间房子。然后用上题解法。

Case 2:相当于抹掉第一间房子。然后用上题解法。

则我们只要求出二者的最大值即可。