代码

发布日期: 2022-07-09

更新日期: 2022-07-10

文章字数: 3.1k

阅读时长: 18 分

动态规划

动态规划步骤

确定DP数组和下标含义。
确定递推公式。
初始化DP数组。
确定遍历顺序。
举例推导DP数组。
动态规划常用题型
背包问题（n个数组成k）
数组中若干数和为k的方法数
背包问题中的组合与排列（内外循环顺序）
最长连续子序列（子序列连续，子序列不连续）
最长递增序列，最大和
字符串子串判定，转换步数

回文字符串

leetcode：509

class Solution {
public:
int fib(int n) {
  if(n<=1) return n;
  vector<int>dp(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];
}
};

leetcode：70

class Solution {
public:
int climbStairs(int n) {
  if(n<=1) return n;
  vector<int>dp(n+1);
  dp[1]=1;
  dp[2]=2;
  for(int i=3;i<=n;i++){
      dp[i]=dp[i-1]+dp[i-2];
  }
  return dp[n];
}
};

leetcode：746

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

leetcode：62

class Solution {
public:
int uniquePaths(int m, int n) {
  int dp[m][n];
  for(int i=0;i<m;i++){
      dp[i][0]=1;
  }
  for(int j=0;j<n;j++){
      dp[0][j]=1;
  }
  for(int i=1;i<m;i++){
      for(int j=1;j<n;j++){
          dp[i][j]=dp[i][j-1]+dp[i-1][j];
      }
  }
  return dp[m-1][n-1];
}
};

leetcode：63

class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
  int m=obstacleGrid.size();
  int n=obstacleGrid[0].size();
  int dp[m][n];
  for(int i=0;i<m;i++) fill(dp[i],dp[i]+n,0);
  for(int i=0;i<m;i++){
      if(obstacleGrid[i][0]==1) break;
      dp[i][0]=1;
  }
  for(int i=0;i<n;i++){
      if(obstacleGrid[0][i]==1) break;
      dp[0][i]=1;
  }
  for(int i=1;i<m;i++){
      for(int j=1;j<n;j++){
          if(obstacleGrid[i][j]==1) continue;
          dp[i][j]=dp[i-1][j]+dp[i][j-1];
      }
  }
  return dp[m-1][n-1];
}
};

leetcode：343

class Solution {
public:
int integerBreak(int n) {
  int dp[n+1];
  fill(dp,dp+n+1,0);
  dp[2]=1;
  for(int i=3;i<=n;i++){
      for(int j=1;j<i-1;j++){
          dp[i]=max({dp[i],(i-j)*j,j*dp[i-j]});
      }
  }
  return dp[n];
}
};

leetcode：96

class Solution {
public:
int numTrees(int n) {
  int dp[n+1];
  fill(dp,dp+n+1,0);
  dp[0]=1;
  for(int i=1;i<=n;i++){
      for(int j=1;j<=i;j++)
      dp[i]+=dp[j-1]*dp[i-j];
  }
  return dp[n];
}
};

leetcode：416

class Solution {
public:
bool canPartition(vector<int>& nums) {
  int sum=0;
  for(int i=0;i<nums.size();i++) sum+=nums[i];
  if(sum%2==1) return false;
  int target=sum/2;
  int n=nums.size();
  int dp[target+1];
  fill(dp,dp+target+1,0);
  for(int i=0;i<nums.size();i++){
      for(int j=target;j>=nums[i];j--){
          dp[j]=max(dp[j-nums[i]]+nums[i],dp[j]);
      }
  }
  if(dp[target]==target) return true;
  else return false;
}
};

leetcode：494

class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
  int all = 0;
  for(int i=0;i<nums.size();i++) all+=nums[i];
  if(abs(target)>all) return 0;
  if( (all+target)%2==1) return 0;
  int res = (all+target)/2;
  int dp[res+1];
  fill(dp,dp+res+1,0);
  dp[0]=1;
  for(int i=0;i<nums.size();i++){
      for(int j=res;j>=nums[i];j--){
          dp[j]+=dp[j-nums[i]];
      }
  }
  return dp[res];
}
};

leetcode：474

class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
  int dp[m+1][n+1];
  for(int i=0;i<m+1;i++) fill(dp[i],dp[i]+n+1,0);
  for(int i=0;i<strs.size();i++){
      int zeronum=0,onenum=0;
      string temp = strs[i];
      for(int j=0;j<temp.size();j++){
          if(temp[j]=='0') zeronum++;
          else onenum++;
      }
      for(int u=m;u>=zeronum;u--)
      {
          for(int v=n;v>=onenum;v--){
              dp[u][v]=max(dp[u-zeronum][v-onenum]+1,dp[u][v]);
          }
      }
  }
  return dp[m][n];
}
};

leetcode：518

class Solution {
public:
int change(int amount, vector<int>& coins) {
  int dp[amount+1];
  fill(dp,dp+amount+1,0);
  dp[0]=1;
  for(int i=0;i<coins.size();i++){
      for(int j=coins[i];j<=amount;j++){
          dp[j]+=dp[j-coins[i]];
      }
  }
  return dp[amount];
}
};

leetcode：377

class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
  int dp[target+1];
  fill(dp,dp+target+1,0);
  dp[0]=1;
  for(int i=0;i<=target;i++){
      for(int j=0;j<nums.size();j++){
          if(i>=nums[j]&&dp[i]<INT_MAX-dp[i-nums[j]]) {
              dp[i]+=dp[i-nums[j]];
          }
      }
  }
  return dp[target];
}
};

leetcode：322

class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
  int dp[amount+1];
  //求最少金币数，则初始化最大，dp[0]为0
  //若是求最多金币数，则初始化0，dp[0]为1
  fill(dp,dp+amount+1,INT_MAX);
  dp[0]=0;
  for(int i=0;i<coins.size();i++){
      for(int j=coins[i];j<=amount;j++){
          //判断是不是初始情况，不是则使用，是则跳过
          if(dp[j-coins[i]]!=INT_MAX)
          dp[j]=min(dp[j],dp[j-coins[i]]+1);
      }
  }
  if(dp[amount]==INT_MAX) return -1;
  else return dp[amount];
}
};

leetcode：279

class Solution {
public:
int numSquares(int n) {
  int dp[n+1];
  fill(dp,dp+n+1,INT_MAX);
  dp[0]=0;
  //物品从1开始
  for(int i=1;i*i<=n;i++){
      //背包从1开始
      for(int j=1;j<=n;j++){
          if(j-i*i>=0){
              dp[j]=min(dp[j],dp[j-i*i]+1);
          }
      }
  }
  return dp[n];
}
};

leetcode：139

class Solution {
public:
  bool wordBreak(string s, vector<string>& wordDict) {
      unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
      vector<bool> dp(s.size() + 1, false);
      dp[0] = true;
      for (int i = 1; i <= s.size(); i++) {   
          // 遍历背包
          for (int j = 0; j < i; j++) {       
              // 遍历物品
              string word = s.substr(j, i - j); 
              //substr(起始位置，截取的个数)
              if (wordSet.find(word) != wordSet.end() && dp[j]) {
                  dp[i] = true;
              }
          }
      }
      return dp[s.size()];
  }
};

leetcode：121

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

leetcode：122

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

leetcode：123

class Solution {
public:
int maxProfit(vector<int>& prices) {
  int n = prices.size();
  int dp[n][4];
  for(int i=0;i<n;i++) fill(dp[i],dp[i]+4,0);
  dp[0][0]=-prices[0];
  dp[0][1]=0;
  dp[0][2]=-prices[0];
  dp[0][3]=0;
  for(int i=1;i<n;i++){
      dp[i][0]=max(dp[i-1][0],-prices[i]);
      dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i]);
      dp[i][2]=max(dp[i-1][2],dp[i-1][1]-prices[i]);
      dp[i][3]=max(dp[i-1][3],dp[i-1][2]+prices[i]);
  }
  return dp[n-1][3];
}
};

leetcode：188

class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
  int n = prices.size();
  if(n==0||k==0) return 0;
  int dp[n][2*k];
  for(int i=0;i<n;i++) fill(dp[i],dp[i]+2*k,0);
  for(int i=0;i<2*k;i+=2) dp[0][i]=-prices[0];
  for(int i=1;i<n;i++){
      for(int j=0;j<=2*k-1;j++){
          if(j==0){
              dp[i][j]=max(dp[i-1][j],-prices[i]);
              continue;
          }
          if(j%2==1) dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+prices[i]);
          else dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]-prices[i]);
      }
  }
  return dp[n-1][2*k-1];
}
};

leetcode：300

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

leetcode：674

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

leetcode：718

class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
  int x=nums1.size();
  int y=nums2.size();
  int dp[x+1][y+1];
  for(int i=0;i<=x;i++) fill(dp[i],dp[i]+y+1,0);
  int res=0;
  for(int i=1;i<=x;i++){
      for(int j=1;j<=y;j++){
          if(nums1[i-1]==nums2[j-1]){
              dp[i][j]=dp[i-1][j-1]+1;
          }
          if(dp[i][j]>res) res=dp[i][j];
      }
  }
  return res;
}
};

leetcode：1143

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

leetcode：1135

class Solution {
public:
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
  int n=nums1.size();
  int m=nums2.size();
  int dp[n+1][m+1];
  for(int i=0;i<=n;i++) fill(dp[i],dp[i]+m+1,0);
  int res=0;
  for(int i=1;i<=n;i++){
      for(int j=1;j<=m;j++){
          if(nums1[i-1]==nums2[j-1]){
              dp[i][j]=dp[i-1][j-1]+1;
          }else dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
          res=max(res,dp[i][j]);
      }
  }
  return res;
}
};

leetcode：53

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

leetcode：392

class Solution {
public:
bool isSubsequence(string s, string t) {
  int n=s.size();
  int m=t.size();
  int dp[n+1][m+1];
  for(int i=0;i<=n;i++) fill(dp[i],dp[i]+m+1,0);
  for(int i=1;i<=n;i++)
  {
      for(int j=1;j<=m;j++)
      {
          if(s[i-1]==t[j-1]){
              dp[i][j]=dp[i-1][j-1]+1;
          }else dp[i][j]=dp[i][j-1];
      }
  }
  if(dp[n][m]==s.size()) return true;
  else return false;
}
};

leetcode：115

class Solution {
public:
int numDistinct(string s, string t) {
  int n=s.size();
  int m=t.size();
  unsigned long long dp[n+1][m+1];
  for(int i=0;i<n+1;i++) dp[i][0]=1;
  for(int i=1;i<m+1;i++) dp[0][i]=0;
  for(int i=1;i<=n;i++)
  {
      for(int j=1;j<=m;j++)
      {
          if(s[i-1]==t[j-1]){
              dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
          }else dp[i][j]=dp[i-1][j];
      }
  }
  return dp[n][m];
}
};

leetcode：583

class Solution {
public:
int minDistance(string word1, string word2) {
  int n=word1.size();
  int m=word2.size();
  int dp[n+1][m+1];
  for(int i=0;i<=n;i++) dp[i][0]=i;
  for(int i=0;i<=m;i++) dp[0][i]=i;
  for(int i=1;i<=n;i++)
  {
      for(int j=1;j<=m;j++)
      {
          if(word1[i-1]==word2[j-1])
          {
              dp[i][j]=dp[i-1][j-1];
          }else
          {
              dp[i][j]=min({dp[i-1][j-1]+2,dp[i-1][j]+1,dp[i][j-1]+1});
          }
      }
  }
  return dp[n][m];
}
};

leetcode：72

class Solution {
public:
int minDistance(string word1, string word2) {
  int n=word1.size();
  int m=word2.size();
  int dp[n+1][m+1];
  for(int i=0;i<=n;i++) dp[i][0]=i;
  for(int i=0;i<=m;i++) dp[0][i]=i;
  for(int i=1;i<=n;i++)
  {
      for(int j=1;j<=m;j++)
      {
          if(word1[i-1]==word2[j-1])
          {
              dp[i][j]=dp[i-1][j-1];
          }else {
              dp[i][j]=min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]})+1;
          }
      }
  }
  return dp[n][m];
}
};

leetcode：647

class Solution {
public:
int countSubstrings(string s) {
  int n=s.size();
  bool dp[n][n];
  int res=0;
  for(int i=0;i<n;i++) fill(dp[i],dp[i]+n,false);
  for(int i=n-1;i>=0;i--)
  {
      for(int j=i;j<n;j++)
      {
          if(s[i]==s[j])
          {
              if(j-i<=1){
                  res++;
                  dp[i][j]=true;
              }else if(dp[i+1][j-1]){
                  res++;
                  dp[i][j]=true;
              }
          }
      }
  }
  return res;
}
};

leetcode：516

class Solution {
public:
int longestPalindromeSubseq(string s) {
  int n=s.size();
  int dp[n][n];
  for(int i=0;i<n;i++) fill(dp[i],dp[i]+n,0);
  for(int i=0;i<n;i++) dp[i][i]=1;
  for(int i=n-1;i>=0;i--)
  {
      for(int j=i+1;j<n;j++)
      {
          if(s[i]==s[j]){
              dp[i][j]=dp[i+1][j-1]+2;
          }else {
              dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
          }
      }
  }
  return dp[0][n-1];
}
};

FFFfrance

http://ffffrance.github.io/2022/070955046.html

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 FFFfrance !

代码

文献阅读：AIOS

2022-10-31 文献阅读

文献阅读

回溯算法

回溯算法，及例题。

2022-07-08 代码

代码

动态规划

动态规划

动态规划步骤

动态规划常用题型

leetcode：509

leetcode：70

leetcode：746

leetcode：62

leetcode：63

leetcode：343

leetcode：96

leetcode：416

leetcode：494

leetcode：474

leetcode：518

leetcode：377

leetcode：322

leetcode：279

leetcode：139

leetcode：121

leetcode：122

leetcode：123

leetcode：188

leetcode：300

leetcode：674

leetcode：718

leetcode：1143

leetcode：1135

leetcode：53

leetcode：392

leetcode：115

leetcode：583

leetcode：72

leetcode：647

leetcode：516

你的赏识是我前进的动力