动态规划

• 数字三角形

  用递归实现，复杂度为

  # include<iostream>
  //max函数在algorithm头文件里
  # include<algorithm>
  using namespace std;
  
  #define MAX 101;
  int N;
  int D[MAX][MAX];
  
  int maxSum(int i,int j){
      if(i == N) return D[i][j];
      else{
          return max(maxSum(i+1,j),maxSum(i+1,j+1])+D[i][j];
      }
  }
  int main(){
      cin >> N;
      for(int i = 0;i<N;i++){
          for(int j = 0;j<=i;j++){
              cin >> D[i][j];
          }
      }
      cout << maxSum(0,0);
  }
  

• 使用动态规划来做

  #include<iostream>
  #include<algorithm>
  #define MAX 101
  using namespace std;
  int N;
  int D[MAX][MAX];
  //一个记录中间运算结果的数组
  int maxSum[MAX][MAX];
  
  int MaxSum(int i,int j){
      //如果已经算过一次，无需再次计算,避免了重复计算降低复杂度
      if(maxSum[i][j] != -1) return maxSum[i][j];
      //如果为最后一行，D[i][j]的值就是maxSum[i][j]的值
      if(i==N) maxSum[i][j] = D[i][j];
      else{
          maxSum[i][j] = max(MaxSum(i+1,j),MaxSum(i+1,j+1))+D[i][j];
      }
      return maxSum[i][j];
  }
  int main(){
      cin >> N;
      for(int i = 0;i<N;i++){
          for(int j = 0;j<= i;j++){
              cin >> D[i][j];
              //给存储中间数据的数组赋一个不可能的初值
              maxSum[i][j] = -1;
          }
      }
      cout << MaxSum(0,0);
  }
  

  • 因为递归要用到函数调用，我们可以直接用递推做，不用调用函数，提高效率

  • 而且递归可能存在递归深度太大，堆栈不够用的情况

#include<iostream>
#include<algorithm>
#define MAX 100
using namespace std;

int N;
int D[MAX][MAX];
int maxSum[MAX][MAX];

int main(){
    cin >> N;
    for(int i = 0;i<N;i++){
        for(int j = 0;j<=i;j++){
            cin >> D[i][j];
        }
    }
    //边界值——最后一行是确定的
    for(int j = 0;j<N;j++){
        maxSum[N][j] == D[N][j];
    }
    //往上递推
    for(int i = n-1;i>=0;i--){
        for(int j = 0;j<=i;j++){
            maxSum[i][j] = max(maxSum[i+1][j],maxSum[i+1][j+1])+D[i][j];
        }
    }
    cout << maxSum[0][0];
}

• 进一步，可以进行空间优化，使用以为数组存储maxSum，因为里面的数是滚动更新的；

• 这也体现了递推的一个优势——有时候可以使用滚动数组

#include <iostream>
#include <algorithm>
#define MAX 100
using namespace std;
int D[MAX][MAX];
int n;
int main(){
    cin >> n;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<=i;j++){
            cin >> D[i][j];
        }
    }
    int * sumMax;
    //建立一个指针指向D[n]，把递推的过程变成更新D[n]中的数
    sumMax = D[n];
    for(int i = n-1;i>=0;i--){
        for(int j = 0;j<=i;j++){
            sumMax[j] = max(sumMax[j],sumMax[j+1]) + D[i][j];
        }
    }
    cout << sumMax[0];
}

• 最长上升子序列问题

  #include <iostream>
  #include <algorithm>
  #define MAX 1000
  using namespace std;
  int a[MAX];
  //建立 一个数组来存放每一个状态
  int maxLen[MAX];
  int n;
  int main(){
     cin >> n;
     for(int i = 0;i<n;i++){
         cin >> a[i];
         maxLen[i] = 1;
     }
     for(int i = 1;i<n;i++){
         for(int j = 0;j<i;j++){
             //maxLen[]是不断更新的，max函数控制是否要更新maxLen
             if(a[i]>a[j]) maxLen[i] = max(maxLen[i],maxLen[j]+1);
         }
     }
      //输出maxLen[]（容器）中最大的一个,第一个参数为起始，左闭右开；在头文件algorithm中
      cout << * max_element(maxLen,maxLen+n);
  }
  

  • 最长子串问题

#include<iostream>
#include<cstring>
#include<algorithm>
#define MAX 1000
using namespace std;

char str1[MAX];
char str2[MAX];
//有两个
int maxLen[MAX][MAX];
int main(){
    while (cin >> str1 >> str2)
    {
        int lenth1 = strlen(str1);
        int lenth2 = strlen(str2);
        int nTmp;
        int i,j;
        //先确定边界状态
        for(i = 0;i < lenth1;i++){
            maxLen[i][0] = 0;
        }
        for(j = 0;j < lenth2;j++){
            maxLen[0][j] = 0;
        }
        //递推式,这里是难点
        for(int i = 1;i<lenth1;i++){
            for(int j = 1;j<lenth2;j++){
                //这里如果不用i-1第一个字母相同不会记录
                if(str1[i-1] == str2[j-1]){
                    maxLen[i][j] = maxLen[i-1][j-1] +1;
                }else{
                //证明，maxLen[i][j]不小于其中的任何一个也不大于其中的任何一个
                    maxLen[i][j] = max(maxLen[i-1][j],maxLen[i][j-1]);
                }
            }
        }
           cout << maxLen[lenth1-1][lenth2-1] << endl;
          
    }
    return 0;
}

• 动态规划问题最难的地方是

  设计状态，找到状态转移的递推关系式

  设计状态的原则：

  是原问题子问题的解

  具有最有子结构（原问题的最优解所包含的子问题，解也是最优的）

  无后效性（只跟当前状态有关，而与怎么抵达这个状态无关）