动态规划(DP)笔记(二): 序列型及简单例题

文章例题

• 1.leetcode 70. 爬楼梯
• 2. leetcode 53. 最大子序列和
• 3. leetcode 198. 打家劫舍

特点：

• 隐式或者显示存在从前往后的顺序
• 动态规划时间复杂度：状态数量 * 后继决策数量 * 转移代价

阶段划分：

• 按照序列顺序从前往后划分

状态表示：

• 状态表示里序列位置作为一维，dp[i] 可以表示：

  1. 第 i 个位置的答案
  2. 前 i 个位置的答案
  3. 前 i 个位置里，第 i 个位置一定选择的答案

• 一维数组 dp[i] 不足以完全表示状态时：

  1. 表达不了的信息加入状态表示，dp[i][a][b][c]
  2. 表达完全后，在优化和合并状态，如 dp[i][x][y]

状态转移方程：

从题目中找到关键句子，分析状态之间的关系，再尝试退出状态转移方程。

代码小技巧：

• 添加不存在初始位置 a_0 ：可以简化边界的初始化，原本的边界变为从 a_0 到该边界的转移，从而只需要初始化 a_0 即可
  

  添加原本不存在的边界 dp[0]

• 主动转移和被动转移：不同题目两种方式代码复杂度不同

  1. 主动转移：一个状态主动寻找它可以转移到的状态 (知道某一状态找其后继容易)

  2. 被动转移：一个状态被更新的时候去寻找哪些状态可以更新它 (知道某一状态找其前驱容易)

     主动转移 / 被动转移

例题

• 1.leetcode 70. 爬楼梯
  

  

  分析
  

  
  1. 递推实现：

  class Solution {
  public:
      int climbStairs(int n) {
          int dp[n + 1];
          dp[0] = dp[1] = 1;      //原地不动和一级台阶方案均为 1
  
          for(int i = 2; i <= n; ++i) {
              dp[i] = dp[i - 1] + dp[i - 2];
          }
  
          return dp[n];
      }
  };
  

  2. 记忆化搜索：

  class Solution {
  public:
      int dp[1005];
  
      int dfs(int n) {
          if(n == 0) return 1;
          if(n < 0) return 0;
  
          if(dp[n] != -1)
              return dp[n];
        
          return dp[n] = dfs(n - 1) + dfs(n - 2);
      }
  
      int climbStairs(int n) {
          memset(dp, -1, sizeof(dp));
          return dfs(n);
      }
  };
  

• 2. leetcode 53. 最大子序列和
  

  

  分析：

  1. 状态表示：
     · dp[i] 以第 i 个数结尾的最大子序列和
  2. 转移方程：
     · 以第 i 个数字结尾的最大子序列和为 其自身( nums[i] )与以其前一个数字为结尾的最大子序列和加上其自身的最大值，即：dp[i] = max(dp[i - 1] + nums[i]，nums[i])
  3. 边界：
     · dp[0] = nums[0]，只有一个数字时最大和为其自身
  4. 注意：
     · 该题求的是最大和

  递推实现：

  class Solution {
  public:
      int maxSubArray(vector<int>& nums) {
          int n = nums.size();
          int dp[n + 1];
          dp[0] = nums[0];
          int ans=dp[0];
  
          for(int i = 1; i < n; ++i) {
              dp[i] = max(nums[i], dp[i - 1] + nums[i]);
              ans = max(ans,dp[i]);
          }
  
          return ans;
     }
  };
  

• 3. leetcode 198. 打家劫舍
  

  

  分析

  1. 状态表示：
     · dp[i] 表示抢劫第 i 家的情况下所获的最大值
  2. 转移方程：
     · 采用被动转移，在抢劫第 i 家的情况下考虑抢劫前 i - 2 家所获最大的方案，即：dp[i] = max(dp[i - 1]，dp[i - 3]) + nums[i]
  3. 边界：考虑到状态转移的 dp[i - 3]，故应该添加一个不存在的初始状态 dp[0] = 0，代码在实现时就转移状态公式的 i 有些修正

  递推实现：

  class Solution {
  public:
      int rob(vector<int>& nums) {
          int n = nums.size();
      
          if(n == 0) return 0;
          if(n == 1) return nums[0];
        
          int dp[n + 1];
          dp[0] = 0;      //添加不存在的边界，方便状态转移
          dp[1] = nums[0];
          dp[2] = nums[1];
  
          for(int i = 3; i <= n; ++i) {
              dp[i] = max(dp[i - 2], dp[i - 3]) + nums[i - 1];      // 对nums[i] 进行了修正
          }
  
          return max(dp[n], dp[n - 1]);
      }
  }
  

参考：

大佬的b站课程
大佬的博文