动态规划

定义：将问题划分为重叠子问题，通过状态转移方程考虑所有可能的选择，并记录子问题的最优解（全局最优）。

一. 最长递增子序列

example1 leetcode 300题

1. 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

• 示例 1：输入：nums = [10,9,2,5,3,7,101,18]
• 输出：4
• 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4

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

二.最长公共子序列LCS

example2 leetcode 095

1. 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
   一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
   例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
   两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

• 示例 1：
• 输入：text1 = "abcde", text2 = "ace"
• 输出：3
• 解释：最长公共子序列是 "ace" ，它的长度为 3 。

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m_size=text1.size();
        int n_size=text2.size();
        vector<vector<int>>dp(m_size+1,vector<int>(n_size+1,0));
        for(int i=1;i<m_size+1;i++)
        {
            for(int j=1;j<n_size+1;j++)
            {
                if(text1[i-1]==text2[j-1])
                {
                    dp[i][j]=max(dp[i-1][j-1]+1,dp[i][j]);
                }
                else
                {
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[m_size][n_size];
    }
};