动态规划(dynamic programming)

dynamic programming (also known as dynamic optimization) is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions – ideally, using a memory-based data structure.

根据维基百科的解释，动态规划是一种解决复杂问题的方法，他将原问题分解为相似子问题的集合，每个子问题只解决一次然后将结果记录下来。

一.dp初识

以下以求斐波那契序列为例，介绍动态规划。
众所周知斐波那契序列式是0，1，1，2，3，5，8…
通常没学过dp的同学，多半会这么解。

int fib(int n){
    if(n==1||n==2) return n-1;
    else return fib(n-1)+fib(n-2);
}

我们可以分析下这么写的时间复杂度，每个递归都将当前问题分解为两个子问题，直到抵达递归基。如此分析可知时间复杂度$O(2^n)$这是无论如何也承受不了的慢。我们可以仔细分析下，主要是大量的重复的计算，对于每个子问题都要计算到递归基为止。这样我们就可以用dp来解决。

int dp[maxn];//初始化为-1
int fib(int n){
    if(dp[n]!=-1) return dp[n];
    else if(n==1||n==2) return n-1;
    else return dp[n]=fib(n-1)+fib(n-2);
}

在此处我们用一个数组dp来记录当前数字是否被记录过，如此这般，就避免了重复的计算。我们可以将递归(recursion)转为迭代(iteration),毕竟这个递归是标准的尾递归(tail-recursion)。

int fib(int n){
    dp[0]=0,dp[1]=1;
    for(int i=2;i<=n;i++)
        dp[i]=dp[i-1]+dp[i-2];
   return dp[n];
}

以上就是动态规划的算法思想。

二.几个例题

以下是几个dp的经典例题。

1最长上升子序列(LIS)

求在一个序列中求长度最长的一个上升子序列。

此题用dp来解，最重要的是如何定义问题使之可以分成几个相似的子问题，在这我们以dp[i]代表以s[i]为结尾的最长上升子序列。

#include<iostream>
#include<algorithm>
#include<cstdio>
//dp[i]代表以s[i]为结尾的最长上升子序列

const int maxn=1000+10;
int s[maxn],dp[maxn];
int main(){
    //freopen("input.txt","r",stdin);
    int N;
    scanf("%d",&N);
    for(int i=1;i<=N;i++){
        scanf("%d",&s[i]);
        dp[i]=1;
    }
    for(int i=2;i<=N;i++){
        for(int j=1;j<i;j++){
            if(s[i]>s[j])
                dp[i]=max(dp[i],dp[j]+1);
        }
    }
    printf("%d",*max_element(dp+1,dp+N+1));
    return 0;
}

此时的时间复杂度是$O(n^2)$.

最大子段和

给出一个整数数组a(正负数都有)，如何找出一个连续子数组（可以一个都不取，那么结果为0），使得其中的和最大？

此题较简单，不再赘述。

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

const int maxn = 50000 + 10;
const int inf = (1 << 29);
int a[maxn];
int main() {
  // freopen("input.txt", "r", stdin);
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  long long partialSum = a[0];
  long long ans=a[0];
  for (int i = 1; i < n; i++) {
      if(partialSum>0) partialSum+=a[i];
      else partialSum=a[i];
     ans=max(ans,partialSum);
  }
 cout<<ans<<endl;
}

最大子矩阵和

一个M*N的矩阵，找到此矩阵的一个子矩阵，并且这个子矩阵的元素的和是最大的，输出这个最大的值。

最大子段和的变体，思路和最大子段和类似，我们通过枚举i,j(0<=i<=j<=n),得到在(i,j)行中的矩阵和，之后再通过最大字段和求解。

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int maxn = 500 + 5;
int a[maxn][maxn];
int c[maxn];
int main() {
 // freopen("input.txt", "r", stdin);
  int m, n;
  cin >> m >> n;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> a[i][j];
    }
  }
  long long ans = 0, finalAns = 0;
  for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
      for (int k = 0; k < m; k++) {
        c[k] = (j == i) ? a[i][k] : c[k] + a[j][k];
      }
      long long partialSum = c[0];
      ans = c[0];
      for (int k = 1; k < m; k++) {
        if (partialSum > 0)
          partialSum += c[k];
        else
          partialSum = c[k];
        ans = max(ans, partialSum);
      }
      finalAns = max(finalAns, ans);
    }
  }
  cout << finalAns << endl;
}

循环数组最大子段和

N个整数组成的循环序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的连续的子段和的最大值（循环序列是指n个数围成一个圈，因此需要考虑a[n-1],a[n],a[1],a[2]这样的序列）。当所给的整数均为负数时和为0。

又一个最大字段和的变体，困难自处在于不知道如何划分数组，自然可以枚举划分，但是效率太低，仔细想想，我们可以不求最大字段和，而是求最小字段和，这样就可以解决，数组划分的问题。

ans=max(maxSubsum,sum-minSubsum)

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;
const int maxn = 50000 + 10;
int a[maxn];
int main() {
  //freopen("input.txt", "r", stdin);
  int n;
  cin >> n;
  long long totalSum = 0;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    totalSum += a[i];
  }

  long long Maxsum = a[0], sum = a[0];
  for (int i = 1; i < n; i++) {
    if (sum > 0)
      sum += a[i];
    else
      sum = a[i];
    Maxsum = max(Maxsum, sum);
  }
  long long Minsum = a[0];
  sum = a[0];
  for (int i = 1; i < n; i++) {
    if (sum < 0)
      sum += a[i];
    else
      sum = a[i];
    Minsum = min(Minsum, sum);
  }
  cout << max(Maxsum, totalSum - Minsum);
}

最小正子段和

还是最大子段和的变种。

N个整数组成的序列a[1],a[2],a[3],…,a[n]，从中选出一个子序列（a[i],a[i+1],…a[j]），使这个子序列的和>0，并且这个和是所有和>0的子序列中最小的。

注意最小正子段和和最小子段和不一样，最小子段和要么为负,要么为0。
我们可以将sum[i]排序，相邻的肯定是最小的正子段和。

#include <algorithm>
#include <cstdio>

using namespace std;

const int maxn = 50000 + 10;
const long inf = (1 << 29);
using elem = pair<long long, int>;
elem sum[maxn];
int a[maxn];
int main() {
  int n;
  scanf("%d", &n);
  sum[0] = make_pair(0, 0);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    sum[i].first = a[i] + sum[i - 1].first;
    sum[i].second = i;
  }
  sort(sum + 1, sum + n + 1);
  long long ans = inf;
  for (int i = 1; i <= n; i++) {
    if (sum[i].first > 0)
      ans = min(ans, sum[i].first);
    if (sum[i].second > sum[i - 1].second && sum[i].first > sum[i - 1].first)
      ans = min(ans, sum[i].first - sum[i - 1].first);
  }
  printf("%lld\n", ans);
}