LeetCode刷题之动态规划算法

1.基本思路及代码框架

首先，动态规划的穷举有点特别，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。

而且，动态规划问题一定会具备「最优子结构」，才能通过子问题的最值得到原问题的最值。

另外，虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，只有列出正确的「状态转移方程」，才能正确地穷举。

以上提到的重叠子问题、最优子结构、状态转移方程就是动态规划三要素。具体什么意思等会会举例详解，但是在实际的算法问题中，写出状态转移方程是最困难的，这也就是为什么很多朋友觉得动态规划问题困难的原因，我来提供我研究出来的一个思维框架，辅助你思考状态转移方程：

明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。

按上面的套路走，最后的结果就可以套这个框架：

# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)

2.题目解答

1.LeetCode之509斐波拉且数列

• 解题思路

  • 第一种，采用递归思想，直接写出递归函数
  • 第二种，记录下每种情况，避免重复计算。

• 代码实现

  1.递归方程

  /*
   * @lc app=leetcode.cn id=509 lang=cpp
   *
   * [509] 斐波那契数
   */
  
  // @lc code=start
  class Solution {
  public:
      int fib(int n) {
          if (n == 0) return 0;
          if (n == 1 || n == 2) {
              return 1;
          }
          return fib(n -1) + fib(n - 2);
      }
  };
  // @lc code=end
  

  2.子状态记录

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

2.LeetCode之322零钱兑换

• 解题思路

  采用动态规划求解，避免递归。找出基础状态，选择，以及目标。写出状态方程：

  

• 代码实现

  class Solution {
  public:
      int coinChange(vector<int>& coins, int amount) {
          vector<int> dp(amount + 1,amount + 1);
  
          dp[0] = 0;
          for (int i = 0; i < dp.size(); i++) {
              for (auto coin : coins) {
                  if (i - coin < 0) {
                      continue;
                  }
                  dp[i] = min(dp[i], 1 + dp[i - coin]);
              }
          }
          return (dp[amount] == amount + 1) ? -1 : dp[amount];
      }
  };
  

3.LeetCode之300最长递增子序列

• 解题思路

  状态转移方程：我们以dp[i]表示以num[i]结尾得最长递增子序列的长度。

  根据这个定义，我们的最终结果（子序列的最大长度）应该是 dp 数组中的最大值。

  int res = 0;
  for (int i = 0; i < dp.length; i++) {
      res = Math.max(res, dp[i]);
  }
  return res;
  

  nums[5] = 3，既然是递增子序列，我们只要找到前面那些结尾比 3 小的子序列，然后把 3 接到最后，就可以形成一个新的递增子序列，而且这个新的子序列长度加一。

  显然，可能形成很多种新的子序列，但是我们只选择最长的那一个，把最长子序列的长度作为 dp[5] 的值即可。

  for (int i = 0; i < nums.length; i++) {
      for (int j = 0; j < i; j++) {
          if (nums[i] > nums[j]) 
              dp[i] = Math.max(dp[i], dp[j] + 1);
      }
  }
  

• 代码实现

  /*
   * @lc app=leetcode.cn id=300 lang=cpp
   *
   * [300] 最长递增子序列
   */
  
  // @lc code=start
  class Solution {
  public:
      int lengthOfLIS(vector<int>& nums) {
          vector<int> dp(nums.size(), 1);
  
          for (int i = 0; i < nums.size(); i++) {
              for (int j = 0; j < i; j++) {
                  if (nums[i] > nums[j]) {
                      dp[i] = max(dp[i], dp[j] + 1);
                  }
              }
          }
  
          int res = 0;
          for(int i = 0; i < nums.size(); i++) {
              res = max(res, dp[i]);
          }
  
          return res;
      }
  };
  // @lc code=end
  

4.LeetCode之1143最长公共子序列

• 解题思路

  明确基础状态，写出状态，做出选择。

  写出状态方程。

• 代码实现

  /*
   * @lc app=leetcode.cn id=1143 lang=cpp
   *
   * [1143] 最长公共子序列
   */
  
  // @lc code=start
  class Solution {
  public:
      int longestCommonSubsequence(string text1, string text2) {
          int m = text1.size(), n = text2.size();
          vector<vector<int>> dp(m + 1,vector<int>(n + 1, 0));
          for (int i = 1; i <= m; i++) {
              for (int j = 1; j <= n; j++) {
                  if (text1[i - 1] == text2[j - 1]) {
                      dp[i][j] = 1 + dp[i - 1][j - 1];
                  } else {
                      dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                  }
              }
          }
          return dp[m][n];
      }
  };
  // @lc code=end
  

5.LeetCode之583两个字符串的删除操作

• 解题思路

  与上一题解法思路一致，只不过最终结果需要转化一下。

• 代码实现

  /*
   * @lc app=leetcode.cn id=583 lang=cpp
   *
   * [583] 两个字符串的删除操作
   */
  
  // @lc code=start
  class Solution {
  public:
      int minDistance(string word1, string word2) {
          int m =word1.size(), n =word2.size();
          vector<vector<int>> dp(m + 1,vector<int>(n + 1, 0));
          for (int i = 1; i <= m; i++) {
              for (int j = 1; j <= n; j++) {
                  if (word1[i - 1] ==word2[j - 1]) {
                      dp[i][j] = 1 + dp[i - 1][j - 1];
                  } else {
                      dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                  }
              }
          }
          return m + n - 2 * dp[m][n];
      }
  };
  // @lc code=end
  

6.LeetCode之712两个字符串的最小ASCII删除和

• 解题思路

  先给出基本状态，明确数组的含义，初始化数组，给出状态，做选择。

• 代码实现

  /*
   * @lc app=leetcode.cn id=712 lang=cpp
   *
   * [712] 两个字符串的最小ASCII删除和
   */
  
  // @lc code=start
  class Solution {
  public:
  
      int minimumDeleteSum(string s1, string s2) {
          int m = s1.size(), n = s2.size();
          vector<vector<int>> dp(m + 1,vector<int>(n + 1, 0));
          for (int i = m - 1; i >= 0; i--) {
              dp[i][n] = dp[i + 1][n] + s1[i];
          }
  
          for (int j = n - 1; j >= 0; j--) {
              dp[m][j] = dp[m][j + 1] + s2[j];
          }
  
          for (int i = m - 1; i >= 0; i--) {
              for (int j = n -1; j >= 0; j--) {
                  if (s1[i] == s2[j]) {
                      dp[i][j] = dp[i + 1][j + 1];
                  } else {
                      dp[i][j] = min(dp[i + 1][j] + s1[i],
                      dp[i][j + 1] + s2[j]);
                  }
              }
          }
          return dp[0][0];
      }
  
  };
  // @lc code=end