动态规划专项讲解

简单dp问题

动态规划简称dp,全称dynamic programming,动态 规划

动态规划是做题的一个重要方法，用来求出一个问题的最优解；动态规划就是把一个问题分成多个阶段，然后一个一个阶段往后推。

动态规划必要的东西（没有就不能用动态规划求解）：  
无后继性：无论通过什么方式达到某种状态后面能做的决策都一样。
能够最优化：就是在各种状态下都能求出最优解，然后我们只需要保留这个最优解继续进行下一阶段。
动态规划术语：
策略：指的是你求出最优解每一步的方案。如方案数，字典序最小的方案等等
状态：目前子问题的情况，局面，比如在搜索时你处于第x行第y列，这就是一个状态。
阶段：第x阶段，有时指的是这步是第x步或者这是第x个数等待。
决策：此时做的操作，比如选不选这个数等等。
状态转移方程：在递归的角度来讲爱你就是递推式，比如斐波那契数列的状态转移方程就是a[i]=a[i-1]+a[i-2]

例题：楼梯有n阶，上楼可以一步上一阶，也可以一步上二阶，编一个程序，计算有多少种走法

输入：楼梯数        输出：走的方式总数

分析：阶段：目前在的台阶数     状态：达到第x级台阶的方案数    决策：每次上一阶还是两阶
我们可以用一个dp数组来存储第x级台阶的方案数。dp[1]=1,dp[2]=2，。。。
可以从第x-1或第x-2级台阶上到第x级台阶，对应的状态就是  dp[x-1  ]和  dp[x-2]
由于这里是求解方案数，所以这里第x阶方案数就是第x-1  + 第x-2的方案数
状态转移方程就是： dp[x] = dp[x-1] +dp[x-2];

dp问题本质上也是递归，这里也要注意边界条件，dp[0] 和dp[1]都是1，因为0级就是不动 1级就是只走一次1级
判断边界还有一个技巧，极速判断下标合不合法（0<=下标<数组长度）；
这个算法的时间复杂度为o(n)

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int dp[5001];//设置dp数组 注意长度开大点
    dp[0]=1;
    dp[1]=1;//边界条件
    for(int i=2;i<=n;i++){
        dp[i]=(dp[i-1]+dp[i-2]);//状态转移方程
    }
    cout<<dp[n];
}

动态规划的本质思想还是递推

题目变形，每次可以走任意奇数级楼梯，对于n（1~1000）有多少种第n级楼梯的方法？
思路：和上一题相似，但是这次一次能走任意奇数级台阶，即1,3,5,7，。。。级楼梯
上一题一次是走1或2级楼梯，所以方案和就是dp[x-1] + dp[x-2];
这次是任意奇数级，所以方案和是dp[i] = dp[i-1]+dp[i-3]+dp[i-5]+...

需要用一个循环计算出dp[i-1]+dp[i-3]+dp[i-5]+...的和，

for(int j=i;j>=0;j-=2){
.......
}

然后每次将dp[i] 加上 dp[j] ，这里能保证j一直小于i
算法的时间复杂度为o(n),每个状态转移的时间复杂度大约为o(n)
这题不用设置边界条件 因为所有的数据都能通过状态转移来算出来（因为dp[0]那i-1<0 就直接是0了）

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int dp[1001];
    memset(dp,0,sizeof(dp));//最好能初始化
    //不用设置边界条件
    for(int i=0;i<n;i++){
        //从0开始转移 因为没有设置边界条件
        for(int j=i-1;i>=0;j-=2){
           dp[i]=dp[i]+dp[j]
        }
    }
}

以上就是简单的dp问题，下一部分会讲倒序的状态转移和二维dp

倒序动态转移：有些题要求在多个起点中选择一个起点，如果从起点开始则不方便我们求解，而且时间复杂度也会很高，所以这时候我们需要倒序动态转移，就是从终点开始逆推；

例题：有一个小球掉落在一串连续的弹簧板上，小球落到某一个弹簧板后，会被弹到某一个地点，直到小球被弹到弹簧板以外的地方。

假设有n个连续的弹簧板，每个弹簧板占一个单位距离，a[i]代表代表第i个弹簧板会把小球向前弹 a[i] 个距离。比如位置1的弹簧能让小球前进2个距离到达位置 3。如果小球落到某个弹簧板后，经过一系列弹跳会被弹出弹簧板，那么小球就能从这个弹簧板弹出来。现在希望你计算出小球从任意一个弹簧板落下，最多会被弹多少次后，才会弹出弹簧板。

输入格式 第一个行输入一个n代表一共有 n(1≤n≤100000)个弹簧板。第二行输入n个数字，中间用空格分开。第i个数字 ai(1≤ai≤30)代表第i个弹簧板可以让小球移动的距离。

输出一个整数，代表小球最多经过多少次才能弹出弹簧板。

思路：这题大家容易想到一种方法：就是枚举每个点然后判断这个点要几步才能跑出边界，然后输出最小值，但是这个算法的时间复杂度大约为o(n^2)，面对n≤100000的数据会tle
所以我们需要时间复杂度更低的算法。

这种o(n^2)算法浪费最长的时间在于最后一段路可能会被走过很多次，但是每次都要重复计数，因为这个弹簧板只会往后弹，所以我们可以从后面的弹簧板开始状态转移
所以我们需要考虑这个弹簧板到弹出弹簧板的步数，但是由于我们是从后往前推的，所以依靠这个弹簧板到达的位置肯定是已经记录过的，如果直接弹出弹簧板则这一状态的步数为0，所以也要把数组开大一些

根据题目我们可以分析出在第i个弹簧板，能弹出的距离是a[i]，所以到达下一个弹簧板就是i+a[i]，因为i+a[i]肯定比i大，所以我们可以直接调用dp[i+a[i]]来获取接下来要走多远才能弹出弹簧板，也需要注意到达这个地方前已经被弹了一次，所以需要+1;

状态转移方程是 dp[i]=dp[i+a[i]] +1;这里dp[i]就是从第i个弹簧板出发弹出弹簧板的次数，也需要注意最终答案是最大弹出次数，所以每次执行都要取一下最大值，如此，这个程序时间复杂度就是o(n)

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a[100001];
    int dp[100050];//这里数组必须开大点，因为会最远弹到弹簧板30格的地方
    memset(dp,0,sizeof(dp));
    int n;
    int ans;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=n;i>=1;i--){
        dp[i]=dp[i+a[i]] +1;
        ans=max(ans,dp[i]);
    }
    cout<<ans;
}

二维dp:二维dp是用来表示一个平面的，当然二维dp也有其他作用，比如说用来表示目前的次数等等。

例题：

类似最短路径，大家应该能想到dfs做法，但是时间复杂度太高了，如果数据范围大就不建议使用，所以这题我们也要用动态规划来解
这题有个特性，每次只能往上或往右，这说明这题是没有后继性的（不能往回走）
我们用dp[i][j]来表示从dp[1][1]（起点）的最优解（就是最短）。对于状态转移，dp[i][j]可以从dp[i-1][j](原本在下面，这次往上走) 或者dp[i][j-1](原本在左边，这次往右走)走到
但是注意这题不是求方案数，而且求最短路，所以我们只需要在dp[i-1][j和dp[i][j-1]中选择一个最短的就行了，也需要加上a[i][j]作为从dp[i-1][j]或 dp[i][j-1]达到这里的距离，所以状态转移方程就是：

dp[i][j]=min(dp[i-1][j],dp[i][j-1])+a[i,j]

这里也需要注意：当i=1时（在最下面一行）不能向dp[i-1][j]转移，当j=1时（最左边一列）不能向dp[i][j-1]转移；当i==1 且 j==1（开始位置） 那么dp[i][j]就是等于0

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    int a[150][150],dp[150][150];
    memset(dp,0,sizeof(dp));
    //把日常的数组开大50位
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==1 && j==1){dp[i][j]=0;//起点，不需要转移}
            else if(i==1){dp[i][j]=dp[i][j-1]+a[i][j];}
            else if(j==1){dp[i][j]=dp[i-1][j]+a[i][j];}
            else{dp[i][j]=min(dp[i-1][j],dp[i][j-1])+a[i][j];}
        }
    }
    cout<<dp[n,n];
}

动态规划之最大子段和问题讲解

子段：一段数字连成的序列，其中连续的一段数字就是子段，子段和就是这一段数字的和。
最大子段和：在一段数字中连成的序列中最大的子段所有数的和就是最大字段和。（子段是否可以为空看题目要求）

最大子段和o(n^3)算法是这样的：

int main(){
    int a[1001];
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int ans=-0x3f3f3f3f;//负无穷
    for(int i=1;i<=n;i++){//枚举左端点
        for(int j=i;j<=n;j++){//枚举右端点
            int sum=0;//计算这段子段的和
            for(int k=i;k<=j;k++){
                sum+=a[k];
            }
            ans=max(ans,sum);//如果这段子段和比目前最大子段和大 就更新
        }
    }
}

o(n^3)算法枚举左端点和右端点 然后算出从左端点到右端点的子段和，最后取最大子段和。
o(n^3)算法可以通过n<=100的数据，但是再大就无法通过了；

我们可以写个前缀来优化暴力算法，每次枚举一个新的左端点就初始化和变量为0  
然后第二层枚举右端点就将和变量加上数组的第右端点位，每次操作及时更新最大值，所以一共有两层循环，时间复杂度o(n^2) 可以通过n<=10000的数据；

int main(){
    int a[1001];
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int ans=-0x3f3f3f3f;//负无穷
    for(int i=1;i<=n;i++){//枚举左端点
        int sum=0;//初始化sum为0
        for(int j=i;j<=n;j++){//枚举右端点
            sum+=a[j];//每次把新的一位加入sum
            ans=max(ans,sum);//如果这段子段和比目前最大子段和大 就更新
        }
    }
}

但是这样还是无法通过n<=100000甚至更高的数据。所以如果要进一步优化，我们就要使用动态规划。

我们先开个dp数组  每次状态转移需要判断dp[i-1]是否大于等于0， 如果大于等于0 那说明前面的子段是可以保留的，再把a[i]接到这后面；如果小于0（比如-2） 那说明前面这段不是最优的

for(int i=1;i<=n;i++){
    if(dp[i-1]>=0){
       dp[i]=dp[i-1]+a[i];
    }else{
       dp[i]=a[i];
      }
//或者压行数的话
dp[i]=max(dp[i-1]+a[i],a[i]);
}

//取其中最大值
int ans=-0x3f3f3f3f;//负无穷初始化
for(int i=1;i<=n;i++){
    ans=max(ans,dp[i]);
}
cout<<ans;

动态规划之最大子矩阵和问题

最大子矩阵问题：给点一个n行m列的矩阵，找出其中和最大的子矩阵，输出和。

样例：
2 2
1 2
-2 1
输出：3
对于这题我们可以想到循环枚举上下左右边界，但是时间复杂度比较大
动态规划做法：固定上下边界，然后通过前缀和来求，我们可以设置一个二维数组sum[i][j]  表示第j列 前i行的和
分析如何初始化数组   sum数组：对于sum[i][j] 首先需要加上sum[i-1][j] 这是第j列前i-1行的和，然后再加上a[i][j],就是第j列第i行的值，然后再套双层循环。

for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
       sum[i][j]=sum[i-1][j]+a[i][j];
       //计算第j列前i行的和
    }
}

在主要代码中，前两层循环负责枚举行的上边界和下边界，设上边界为i，下边界为j,第三层循环为枚举列，设列位k,那么新的一维数组tmp就是sum[j][k]-sum[i-1][k](这是前缀和的代码)
可以先将新的数组tmp给算出来，然后o(n)时间内执行最大子段和问题就行了。
需要注意在第三层循环外面设置ans变量，然后ans变量在每次最大子段和实时更新
时间复杂度为o(n^3)，可以通过n在200~400的数据

#include<bits/stdc++.h>
using namespace std;
int main(){//这种矩阵题数据范围可能超过int 需要long long
    int n,m;
    long long int a[101][101],sum[101][101];
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            sum[i][j]=sum[i-1][j]+a[i][j];
            //计算第j列前i行的和（即计算当前元素所在列的前缀和）
        }
    }
    long long int ans=-1e8;//long long的负无穷更大一点
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            long long int tmp[101];
            for(int k=1;k<=m;k++){
                //在sumu数组的范围内以i为上边界 j为下边界作前缀和
                tmp[k]=sum[i][k]-sum[i-1][k];
            }
            long long int cur=0;
            for(int k=1;k<=m;k++){//标准最大子段和
                 cur=max(tmp[k],cur+tmp[k]);
                 ans=max(ans,cur);
            }
        }
    }
    cout<<ans;
}

（不太明白qaq,先写着记下来吧）

c++知识点之滚动数组对节省空间的妙用

某些动态规划题需要使用到二维dp数组，比如说需要转移的不是一个数而是一个数量（比如背包问题，后面会讲到）
c++的数组最大空间要求是1亿，超出1亿则开不了，对于需要转移1万次以上的1万个数据（或者其他情况），则不能直接设置二维数组，我们这时需要用到滚动数组。 
使用滚动数组时我们需要观察计算第n行结果时 需要用到那几行结果
举个例子，比如说对于斐波那契数列（一维），转移第n项时 需要用到n-1 和n-2项，这两项就有必要储存，其他则不需要
所以我们就可以设置一个长度为3的数组，第0位存储第n-2项，第1位存储第n-1项，第2位存储第n项。计算第i项时，不使用滚动数组的状态转移方程是dp[i]=dp[i-1]+dp[i-2],使用后就是dp[2]=dp[0]+dp[1];(i>=2即成立)。

每次转移完成后，对于第i+1次转移 我们只需要第i-1项（原本的dp[1]）和第i项（原本的dp[2]）,而第i+1次转移使用的是dp[2],与原本的dp[2]撞车了，我们就需要把原本的dp[2]移到dp[1], 把原本的dp[1]移到dp[0], 原本的dp[0]（第i-2项）这时候用不到了，就不要了，然后再次状态转移。

这样原本的空间复杂度就是o(n),现在的空间复杂度就是o(1).代码如下：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int dp[3];
    memset(dp,0,sizeof(dp));
    dp[0]=1;
    dp[1]=1;
    //初始化边界数据
    for(int i=2;i<=n;i++){
        dp[2]=dp[0]+dp[1];//dp[i]=dp[i-1]+dp[i-2];
        dp[0]=dp[1];
        dp[1]=dp[2];
        //把所有数据向左移1位  为下次状态转移做准备
    }
    cout<<dp[2];//dp[2]则为最后一次状态转移得出的数
    //最后一次状态转移dp[n(2)]=dp[n-1(1)]+dp[n-2(0)]
    //dp[1]也可 第n次状态转移（最后一次）结束后dp[1]赋值为dp[2]
}

整体与前面讲的题差不多，但是注意要多套一维。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int dp[100][3];

    for(int i=0;i<2;i++){
       for(int j=0;j<n;j++){
           cin>>dp[j][i];
        }
    }
    //注意输入顺序
    for(int i=0;i<n;i++){
       for(int j=2;j<=10;j++){
           dp[i][2]=dp[i-1][1]+dp[i-1][0];
           dp[i][0]=dp[i][1];
           dp[i][1]=dp[i][2];
           //这两句代码顺序不要搞反
        }
        cout<<dp[i][2]<<endl;
    }
}

动态规划：最长上升子序列问题

lis(longest increasing subsequence)问题，即最长上升子序列问题，是一个动态规划的经典模型
子序列：某个序列的子序列是从最初序列通过去除某些元素但不破坏余下元素的相对位置（在前或在后）而形成的新序列
最长上升子序列：在给定序列中选择一个长度最长的且数值严格递增的子序列。
子序列可以为原序列，且可以不唯一
比如：2 1 4 7 5 6 3的最长上升子序列为2 4 5 6 或1 3  5 6  长度为4

我们先来缺点这题的dp数组设定：
先设定dp[i]表示前i个数的最长上升子序列。考虑到状态转移，我们需要记忆前i个数的最长上升子序列的最后一位。转移时（这里指第i位）我们需要遍历dp[0]到dp[i-1]，选择对应下标的数（指前i个数最长上升子序列的最后一位）比a[i]小且对应下标的最长子序列最长。然后没有匹配就把a[i]设定为最长上升子序列的第一位，dp[i]就是1。
这种方法是可行的，但是需要多开数组且代码更加繁琐。
我们考虑换一种状态设定方法，在原本的状态设定方法中我们需要储存前i个数最长上升子序列的最后一位，我们可以优化下这一点，设置前i个数的最长上升子序列必须包含a[i]，也就是前i个数的最长上升子序列的最后一位必须是a[i]。
​​​​​​​对于状态转移（这里是指第i位），我们可以遍历dp[0]到dp[i-1]，选择其中下标对应的数（指a[j]）小于a[i]且dp[j]最大。（就是选择一个最长的可以把a[i]给放到最后的子序列）
我们可以在第二层循环开始前先设置dp[i]为1（一个数可以组成），然后如果每次有匹配的数就与dp[i]和dp[j]+1（dp[j]为序列原本长度，加上a[i]后序列长度应该+1）取最大值
最后再从遍历整个dp数组选出最大的。代码如下：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a[100000],dp[100000];
    int n;
    cin>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<n;i++){
        dp[i]=1;
        //如果没有可以把a[i]加到最后的序列就自成一个序列
        for(int j=0;j<i;j++){
           if(a[j]<a[i]){
              //如果可以把a[i]加到以a[j]结尾的序列里
              dp[i]=max(dp[i],dp[j]+1);
           }
        }
    }
    int ans=0;
    for(int i=0;i<n;i++){
        ans=max(ans,dp[i]);
        //并不是以最后一位结尾的序列是最长的  所以需要遍历以任何一位结尾的序列的长度
    }
    cout<<ans;
}

如果题目要求最长不下降子序列，最长下降子序列，最长不上升子序列等，只需要改变a[j]和a[i]的判断条件就可以了（上述代码第14行）。
最长不下降子序列：if(a[j]<=a[i])
最长不上升子序列：if(a[j]>=a[i])
最长下降子序列：if(a[j]>a[i])

本篇内容参考b站视频https://space.bilibili.com/1166794846/channel/collectiondetail?sid=776678&ctype=0