算法初步|动态规划

贪心算法：

  • 每部最优；
  • f(n)=f(n-max(i)+1)

动态规划

  • 子结构最优
  • f(n)=min{f(n-i1),f(n-i2),f(n-i3)}+1

适用条件：

  • 子结构最优
  • 无后效性

案例：

  1. DAG 有向无环图最短路


    image.png

思路：
F(T)=min(F(T.inEdgeTraverse(T)))
代码：

2.最长上升子序列
思路：dp[i]=max{dp[i],max{dp[0:i-1]}+1}

#include<bits/stdc++.h>
int num;
int data[100];
int dp[100];

int DP()
{
for (int i=1;i<=num;i++)
  {
    for(int j=1;int j<i;j++)
    {
      if(data[j]<data[i]){ dp[i]=max{dp[i],dp[j]+1};}
    }
  }
}
int main()
{
  cin>>num;
  for(int i=0;i<num;i++)
  {
    cin>>data[i];
    dp[i]=1;
  }
  cout<<DP();
}

算法分析：复杂度为O(n^2)
算法优化：O（nlogn）贪心算法。
  1. 最长子序和
    思路：抛弃负值
#include<bits/stdc++.h>
using namespace std;
int num;
int data[100];
int DP (int *arr) {
    int len=num;
    int [] dp=new int[len];
    dp[0]=arr[0];
    int maxSum=arr[0];
    for(int i=1;i<len;i++){
      dp[i]=Math.max(dp[i-1],0)+arr[i];
      maxSum=Math.max(maxSum,dp[i]);
    }
    return maxSum;
  }

void main(){
  cin>>num;
  for(int i==0;i<num;i++){cin>>data[i];}
  Cout<<DP(data);
}

4.编辑距离


image.png
#include<bits/stdc++.h>
using namespace std;
int ans;

public int MinDistance(string word1,string word2){
  int len1=word1.length;
  int len2=word2.length;
  int [][]dp=new int (len1+1,len2+1);
  for(int i=0;i<len1;i++){dp[i][0]=i;}
  for(int j=0;j<len2;j++){dp[0][j]=j;}
  for(int i=1;i<len1;i++){
    for(int j=1j<len2;j++){
      if(word1.charAt[i-1]==word2.charAt[j-1]) { dp[i][j]=dp[i-1][j-1]; }
      else { dp[i][j]=Math.min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])+1;}
    }
  }
return dp[len1][len2];
}
  1. 青蛙上台阶 lc70
    转移方程：dp[i]=dp[i-1]+dp[i-2]
#include<bits/stdc++.h>
using namespace std;
int DP(int n){
  int [] dp=new int (n+1);
  dp[0]=0;
  dp[1]=1;
  for(int i=2;i<n+1;i++) { dp[i]=dp[i-1]+dp[i-2]; }
  return dp[n];
}
  1. 机器人位移 lc63
int DP(int n,int m){
  int [][] dp=new int(n,m);
  dp[0][0]=0;
  for(int i=0;i<n;i++) {dp[i][0]=1};
  foro(int j=0;j<m;j++) { dp[0][j]=1; }
  for(int i=1;i<n;i++){
    for(int j=1;j<n;j++){
      dp[i][j]=dp[i-1][j]+dp[i][j-1];
    }
  }
  return dp[i-1][j-1];
}

  1. 最长公共子序列 lc300


    image.png
int MaxCommonSubSequence(string word1,string word2){
  int len1=word1.length;
  int len2=word2.length;
  int [][]dp=new int (len1+1,len2+1);
  dp[0][0]=0;
  for (int i=1;i<=len1;i++){
    for(int j=1;j<=len2;j++){
      if(word1[i-1]==word[j-1]) { dp[i][j]=dp[i-1][j-1]+1; }
      else  { dp[i][j] = max{dp[i][j-1],dp[i-1][j]; }
    }
  }
  return dp[len1][len2];
}
  • 注意：转移方程不可以写成
if(subStr1[-1]==subStr2[-1]){
  dp[i][j]=max(dp[i-1][j-1],dp[i][j-1],dp[i-1][j]);
}

反例： acc,ac。dp[i-1][j]=2,dp[i][j]仍为2。

  1. 最长公共子串
int MaxCommonSubStr(string word1,string word2){
  int * lens= new int [2]{word1.length,word2.length};
  int [][]dp=new int(lens[0],lens[1]);
  int ans=0; 
  for(int i=0;i<lens[0];i++) { 
    if(word1[i]== word2[0] ) {
      dp[i][0]=1;
    }
  }
  for(int j=0;j<lens[1];j++) { 
    if(word1[0]== word2[j] ) {
      dp[0][j]=1;
    }
  }
  for(int i=1;i<lens[0];i++) { 
    for(int j=1;j<lens[1];j++){
      if(word1[i]==word2[j]) { dp[i][j]=dp[i-1][j-1]+1 ; }
      else{dp[i][j]=0;}  
      ans=Math.max(dp[i][j],ans);
    }
  }
  return ans;
}
  1. 最长回文子串
    思路1：倒置后求最长公共子串
class Solution {
public:
  int getLongestPalindrome(string word){
      int len=word.length(); 
      int ans=0;
      int dp[len][len];
      for(int i=0;i<len;i++){
          for(int j=0;j<len;j++){
              dp[i][j]=0;
          }
      }
      for(int i=0;i<len;i++){ if(word[i]==word[len-1]) dp[i][len-1]=1;}
      for(int j=len;j>0;j--){if(word[j-1]==word[0]) dp[0][j-1]=1;}
      for(int i=1;i<len;i++){
        for(int j=len-2;j>=0;j--){
          if(word[i]==word[j])  {  dp[i][j] = dp[i-1][j+1]+1 ; }
          ans=max(ans,dp[i][j]);
        }
      }
      return ans;
  }
};

更容易理解的写法

class Solution {
public:
  int getLongestPalindrome(string word){
      int len=word.length(); 
      int ans=0;
      int dp[len][len];
      char str2[len];
      for(int i=0;i<len;i++){
          for(int j=0;j<len;j++){
              dp[i][j]=0;
          }
      }
      int i=len-1;
      for(int k=0;i>=0;i--){str2[k++]=word[i];}
      for(int i=0;i<len;i++){ if(word[i]==str2[0]) dp[i][0]=1;}
      for(int j=0;j<len;j++){if(str2[j]==word[0]) dp[0][j]=1;}
      for(int i=1;i<len;i++){
        for(int j=1;j<len;j++){
          if(word[i]==str2[j])  {  dp[i][j] = dp[i-1][j-1]+1 ; }
          ans=max(ans,dp[i][j]);
        }
      }
      return ans;
  }
};

三思后发现这种算法其实不可取，如出现"abcdecacdcba"的字符串时，算法会将abcd当成回文
正常的DP思路：

d[i][j]=d[i+1][j-1]&&s[i]==s[j]?true:false;

class Solution {
public:
  int getLongestPalindrome(string word){
      int len=word.length(); 
      if(len==0)return 0;
      int ans=1;
      bool dp[len][len];
      for(int i=0;i<len;i++){
          for(int j=0;j<len;j++){
              dp[i][j]=false;
          }
      }
      for(int i=0;i<len;i++){
        dp[i][i]=true;
        if(i<len-1&&word[i]==word[i+1]) {
            dp[i][i+1]=true;
            ans=2;
        }
      }
      for(int l=3;l<=len;l++){
          for(int i=0;i<len-l+1;i++){
              int r=l+i-1;
              if(word[i]==word[r]&&dp[i+1][r-1]){
                  dp[i][r]=true;
                  ans=max(ans,l);
              }
          }  
      }
      return ans;
  }
};

Tips:

  • 双重循环的外循环必须为l，因为dp表为：


    image.png

    转移方程为dp[i][j]<--dp[i+1][j-1];（j>=i）
    先对dp[i][i]赋值，ans=1
    由于可以通过dp[i][i]->dp[i][i+1]，可先初始化两个对角线，ans=2
    (注意ans=2的递推和普遍公式（ans>=3）不一致)，而这两部转移的复杂度是O（n），不怎么影响时间。

for(int i=0;i<len;i++){
        dp[i][i]=true;
        if(i<len-1&&word[i]==word[i+1]) {
            dp[i][i+1]=true;
            ans=2;
        }
 }

再通过一般转移方程得到最终答案。

  • 中心扩展思路
class Solution {
public:
  int getLongestPalindrome(string word){
      int ans=0;
      if(word.size()<2){return word.size();}
      if(word.size()==2){return word[0]==word[1]?2:1;}
      for(int i=1;i<word.size()-1;i++){
          int len1=GetMaxLen(word, i, i);

          int len2=GetMaxLen(word, i, i+1);
           if(i==1){cout<<len2<<endl;}
          ans=max(ans,max(len1,len2));
      }
      return ans;
  }
  int GetMaxLen(string s,int l,int r){
      while(l>=0&&(r<s.size())&&s[l]==s[r]){
          l=l-1;
          r=r+1;
      }
      return r-l-1;
  }
};
  1. 单词拆分
class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
        int len = s.length();
        bool dp[len+1];
        for(int i=1;i<=len;i++){dp[i]=false;}
        dp[0]=true;
        for(int i = 1;i <= len; i++)
            {
            
            for(int j = i-1; j >= 0; j--)
                {
                if(dp[j] && dict.find(s.substr(j,i-j))!= dict.end())
                    {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[len];
    }
};

另一种写法：
思路：

  • 若中间出现非字典单词，则无需向后判断
  • 可从每个位置的字符串出发，扫描是否存在字典单词，若存在则在字符串中的该单词末尾记为true；
  • 若字符串结尾字符被记为true，则该字符串可拆分。

  • 转移方程：


    image.png
class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
        int len = s.length();
        vector<bool>dp(len+1,false);
        dp[0]=true;
        for(int i = 0;i < len; i++)
            {
             for (auto word = dict.begin(); word != dict.end(); ++word)
             {
                 int wordlen=(*word).length();
                 if(i>=wordlen-1 && dp[i-wordlen+1] && s.substr(i-wordlen+1,wordlen)==*word)
                 {
                     dp[i+1]=true;
                 }
             }
        }
        return dp[len];
    }
};
知识点
  • unordered_set的find：返回的是unordered_set::iterator类型
dict.find(s.substr(j,i-j))!= dict.end()
  • unordered_set的traverse：（iterator可以自增）
for (auto word = dict.begin(); word != dict.end(); ++word)

或

for (unordered_set::iterator word = dict.begin(); word != dict.end(); ++word)
  • vector创建定长数组：
vector<type>name(size,初始值);
  • string.substr(pos，len)
  1. 三角最小路径
class Solution {
public:
    int minTrace(vector<vector<int> >& triangle) {
        // write code here
        int len=0;
        for(int i=0;i<triangle.size();i++){
            for(int j=0;j<triangle[i].size();j++){len++;}
        }
        vector<int>dp(len,0);
        dp[0]=triangle[0][0];
        int start=0;
        int end=0;
        for(int i=1;i<triangle.size();i++){
            start+=triangle[i-1].size();
            end=start+triangle[i].size()-1;
            dp[start]=triangle[i][0]+dp[start-triangle[i-1].size()];
            dp[end]=triangle[i][triangle[i].size()-1]+dp[end-triangle[i].size()];
        }
        if(len>1){start=1;}
        for(int i=2;i<triangle.size();i++){
            start +=triangle[i-1].size();
            for(int j=1;j<triangle[i].size()-1;j++){
                dp[start+j]=triangle[i][j]+min(dp[start+j-triangle[i].size()],dp[start+j-triangle[i].size()+1]);
            }
        }

        int minLen=2147483647;
        for(int i=0;i<triangle[triangle.size()-1].size();i++){
            minLen=min(minLen,dp[start+i]);          
        }
        return minLen;
    }
};
  1. 最大正方形 lc221
class Solution {
public:
    int solve(vector<vector<char> >& matrix) {
        // write code here
        bool dp[matrix.size()][matrix[0].size()];
        int ans=0;
     
        for(int i=0;i<matrix.size();i++) { dp[i][0]=matrix[i][0]=='1'?1:0; }
        for(int j=0;j<matrix[0].size();j++) { dp[0][j]=matrix[0][j]=='1'?1:0; }
        for(int i=1;i<matrix.size();i++){
            for(int j=1;j<matrix[0].size();j++){
                if(matrix[i][j]=='0'||matrix[i-1][j]=='0'||matrix[i][j-1]=='0'||matrix[i-1][j-1]=='0'){
                    dp[i][j]=0;
                }
                else{
                    dp[i][j]=min(min(dp[i-1][j-1],dp[i-1][j]),min(dp[i][j-1],dp[i-1][j]))+1;
                    ans=dp[i][j]>ans?dp[i][j]:ans;
                }
            }
        }
        return ans*ans;
    }
};
  1. 矩阵检索 lc304
  • 暴力解法
双循环累加

  • 前缀和优化
    转移方程：


    image.png

    代码：

class NumMatrix {
    int[][] dp;
    
    public NumMatrix(int[][] matrix) {‘
    dp[i][j]的值为(0,0)到(i,j)的面积
        if(matrix.length==0||matrix[0].length==0)
            return;
        int m=matrix.length;
        int n=matrix[0].length;
        dp=new int[m+1][n+1];
        dp[0][0]=matrix[0][0];
        
        for(int i=1;i<m;i++)
            dp[i][0]=dp[i-1][0]+matrix[i][0];
        for(int j=1;j<n;j++)
            dp[0][j]=dp[0][j-1]+matrix[0][j];
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+matrix[i][j];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
    按照转移方程加加减减，注意边界条件
        if(row1==0){
            if(col1==0){
                return dp[row2][col2];
            }else{
                return dp[row2][col2]-dp[row2][col1-1];
            }
        }else{
            if(col1==0)
                return dp[row2][col2]-dp[row1-1][col2];
            else
                return dp[row2][col2]-dp[row1-1][col2]-dp[row2][col1-1]+dp[row1-1][col1-1];
        }
    }
}
  1. 零钱兑换 lc322
class Solution {
public:

    int minMoney(vector<int>& arr, int aim) {
        // write code here
        int dp[aim+1];
        dp[0]=0;
        if(aim>0){dp[aim]=-1;}
        int minValue;
        for(int i=0;i<arr.size();i++){if(aim>=arr[i]) dp[arr[i]]=1;}
        for(int i=1;i<=aim;i++){
            minValue=2147483647;
            for(int j=0;j<arr.size();j++){
                if(i>=arr[j]&&dp[i-arr[j]]>-1){
                    minValue=min(minValue,dp[i-arr[j]]);
                }
             if(minValue!=2147483647){ dp[i]=minValue+1;}
             else{dp[i]=-1;}
            }
        }
        return dp[aim];
    }
};

15.Floyd算法：

void Floyd(MGraph G[M][N],int Path[M][N])

{
  int A[M][N];
  int Path[M][N];
  for(int i=0;i<M;i++){
    for(int j=0;j<N;j++){
        A[i][j]=G[i][j];
        Patj[i][j]=-1;
     }
   }
  for(int v=0;v<VertexNum;v++)
    {
     for(int i=0;i<M;i++)
     {
        for(int j=0;j<N;j++)
        {
         if(A[i][v]+A[v][j]<A[i][j])
            {
              A[i][j]=A[i][v]+A[v][j];
              Path[i][j]=v;
            }
        }
      }  
   }
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容