哈哈，今天来放松放松，来讲讲线性dp，也就两个知识点，希望通过今天的讲解，你会掌握哦
（提示：下文小括号里的内容是小编插话，可忽略）
----------------------------------------------------------分割线--------------------------------------------------------------
一、最大的连续子段和
【问题描述】
给定n个整数(可正可负)组成的序列a1,a2,…,an,求该序列的最大的连续子段和。如果所有整数都是负数，那么定义其最大子段和为0.
【动脑思考】
【解题思路1】暴力枚举
：但是时间复杂度O(n^2) 局限性，易超时
(那我们来看看他的解题思路，最起码能骗几十分）
双重for循环，第一层枚举子段的开头，第二层枚举子段的结尾
int的极大值0x7fffffff这个用起来有可能会误操作，比如+1+2之后实际上就超过；
int minn=0x3f3f3f3f这个值大概是10亿多一点，这个大部分题目都可以的
int maxn=-0x7fffffff,初始化为负数的int范围内极小值
那就优化呗
（可是，还是不太行…… And now, it's time for the miracle to happen.）
【解题思路2】动态规划
定义一个dp数组，定义dp[i]是以 a[i]为结尾的最大连续子段和
（全场中重重重重重点↑）
（相当于与前面的组合不需要展开了）
定义一个dp数组，定义dp[i]是以a[i]为结尾的最大连续子段和
如果dp[i-1]>0，无论a[i]为何值，那么dp[i]=dp[i-1]+a[i]是最大
如果dp[i-1]<=0，无论a[i]为何值，dp[i]=a[i];
【小试牛刀】
（废话不多说，那道题练练）
最大子段和
题目描述
给出一段序列，选出其中连续且非空的一段使得这段和最大。
输入格式
输入文件maxsum1.in的第一行是一个正整数N，表示了序列的长度。
第2行包含N个绝对值不大于10000的整数A[i]，描述了这段序列。
输出格式
输入文件maxsum1.out，仅包括1个整数，为最大的子段和是多少。子段的最小长度为1。
输入输出样例
输入样例1：
7 2 -4 3 -1 2 -4 3输出样例1：
4说明
【样例说明】
2 -4 3 -1 2 -4 3
【数据规模与约定】
对于40%的数据，有N ≤ 2000。
对于100%的数据，有N ≤ 200000。
#include<bits/stdc++.h>
using namespace std;
int a[200010],dp[200010];
int main(){// 最大子段和int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}dp[1]=a[1];int maxn=dp[1];for(int i=2;i<=n;i++){dp[i]=max(dp[i],dp[i-1]+a[i]);maxn=max(maxn,dp[i]);}cout<<maxn;return 0;
}二、 数字三角形
【问题描述】
有一个由非负整数组成的三角形，第一行只有一个数，除了最下面一层之外每个数的左下方和右下方各有一个数，从第一行的数开始，每次可以往左下或右下走一格，直到走到最下行，把沿途经过的数全部加起来。如何走才能使得这个和尽量大？
【问题】：一个n层的数字三角形，完整路线有多少条？
（看上图，理解以下文字）
① 对于(2,1)来说，从(1,1)到(2,1)只有一条路径到达(2,1)的最大和是dp[2][1]=a[1][1]+a[2][1]
② 对于(2,2)来说，从(1,1)到(2,2)只有一条路径到达(2,2)的最大和是dp[2][2]=a[1][1]+a[2][2]
③ 对于(3,2)来说，可以从(2,1)过来也可以从(2,2)过来，要想使得和更大，选择从dp[2][1]与dp[2][2]的较大者过来，dp[3][2]=a[3][2]+max(dp[2][1],dp[2][2])
④ 对于(i,j)来说，可以从左上(i-1,j-1)的位置过来也可以从(i-1,j)过来，要想使得和更大，选择从较大者过来，dp[i][j]=a[i][j]+max(dp[i-1][j],dp[i-1][j])
⑤ 从(1,1)到(4,1)算是从顶层到达底层，同样到(4,2) (4,3) (4,4)都满足，问题的答案是dp[4][1]、dp[4][2]、dp[4][3]、dp[4][4]的最大值
【小试牛刀】
数字三角形 Number Triangles [USACO1.6]
题目描述
观察下面的数字金字塔.
写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。
在上面的样例中,从 7 到 3 到 8 到 7 到 5 的路径产生了最大和:30
输入格式
第一个行一个整数 R(1<= R<=1000) ,表示行的数目.
后面R行，每行多个数，是这个数字三角形这一行包含的所有数字.所有的数字是非负的整数且不大于 100.
输出格式
一行，一个整数，表示那个可能得到的最大的和.
输入输出样例
输入样例1：
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5输出样例1：
30
/*图中给的三角形虽然是直角三角形，
对于第i层的第j个数(i,j)来说，
dp[i][j]仍然等于a[i][j]+max(dp[i-1][j-1],dp[i-1][j])*/
#include<bits/stdc++.h>
using namespace std;
int a[1010][1010],dp[1010][1010];
int main(){int n;cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){cin>>a[i][j];}}dp[1][1]=a[1][1];for(int i=2;i<=n;i++){for(int j=1;j<=i;j++){dp[i][j]=a[i][j]+max(dp[i-1][j],dp[i-1][j-1]);}}int maxn=0;for(int j=1;j<=n;j++){maxn=max(maxn,dp[n][j]);}cout<<maxn;return 0;
} 
（知识点到此结束，接下来看看题吧）
三、例题精讲
方案数
题目描述
有一个类似弹球的游戏，如下图所示。
小球从上向下滑落，每次到一个“交叉”点都有2种选择：向左或向右滑落。如果有一个球从顶端滑落到底，有多少种不同的方法？但是中间有一些“交叉”点是“陷阱”，小球滑到“陷阱”就不能继续下滑了。
输入格式
第一行，两个正整数N,M（1＜N,M＜20），N表示三角形的层数，M表示陷阱的个数
第2行到M+1行，每行2个整数x,y，表示第x行的第y个“交叉”点是“陷阱”
输出格式
小球从上到下的方案数
输入输出样例
输入样例1：
4 3 3 2 3 2 3 2输出样例1：
4说明
输入样例描述的是如下的三角形
【耗时限制】1000ms 【内存限制】128MB
如果题目中不存在陷阱，那么此题就是数字三角形问题,ans = max (dp[n][i]) ，对于dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])
想一下，如果位置(i,j)处是陷阱的话，那么dp[i][j]应该等于什么？
答：dp[i][j] = 0 因为无论左上角和右上角的值是多大，都无法到达(i,j)这个位置
如果(i,j)处是陷阱的话dp[[i][j]=0 ,如果不是陷阱 dp[i][j]=max(dp[i-1][j-1],dp[i-1][j]),如何判断是不是陷阱？
答：陷阱的位置题目都给定了，只需要在读数据的时候，额外定义数组用来标记位置（i,j）是不是陷阱，如果是陷阱就标记数组的值为1，如果不是就标记为0
（到达底层任意一个位置都是到达底层了，所以方案数等于到达底层的所有方案的总和，即所有dp[n][i]的和）
#include<bits/stdc++.h>
using namespace std;
bool t[25][25];
int dp[25][25];
int main(){int n,m;cin>>n>>m;while(m--){int x,y;cin>>x>>y;t[x][y]=1;}if(t[1][1]==1) dp[1][1]=0;else dp[1][1]=1;for(int i=2;i<=n;i++){for(int j=1;j<=i;j++){if(t[i][j]==1) dp[i][j]=0;else dp[i][j]=dp[i-1][j-1]+dp[i-1][j];}}int sum=0;for(int j=1;j<=n;j++){sum+=dp[n][j];}cout<<sum;return 0;
}体验积分值
题目描述
卡卡西和小朋友们做完了烧脑的数字游戏，决定放松一下，他们来到了万达乐园，乐园中有很多的游玩项目，每玩一个项目就能获取一定的体验积分，不同的项目产生不同的体验积分，假设乐园所有的游乐项目正好排成一排，并且游客们不能游玩任意相邻的两个项目，那么卡卡西如何挑选游玩项目，使得这次万达行他能获得最多的体验积分值呢。
输入格式
输入共两行，第一行是一个正整数 n，表示万达乐园的游乐项目数。第二行是 n 个用空格隔开的正整数，分别表示每个游乐项目的体验积分值。
输出格式
只有一个正整数，为最多的体验积分值。
输入输出样例
输入样例1：
5
3 10 8 20 21
输出样例1：
32
输入样例2：
5
3 17 8 20 21
输出样例2：
38
说明
样例1说明：一共 5 个游玩项目，卡卡西选择第一个、第三个和第五个游玩，可共可获得 3+8+21=32 的体验积分值。
样例2说明：一共 5 个游玩项目，卡卡西选择第二个和第五个游玩，可共可获得17+21=38 的体验积分值。
数据范围:
5≤n≤1000 1≤每个游玩项目体验积分值≤500
对于第i个项目来说，
Ø 如果玩项目i,能够得到的积分是a[i]，项目i-1就不能玩了，那么玩到项目i为止能够到的的积分是前i-2个项目的最大积分值dp[i-2]+a[i]
Ø 如果不玩第i个项目，那么能够得到的积分值是前i-1个能够获得的最大积分值dp[i-1]
Ø 那么dp[i]就是两种方案的较大者，即dp[i]=max(dp[i-2]+a[i],dp[i-1])
#include<bits/stdc++.h>
using namespace std;
int dp[1010];
int a[1010];
int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}dp[1]=a[1];for(int i=1;i<=n;i++){dp[i]=max(a[i]+dp[i-2],dp[i-1]);}cout<<dp[n];return 0;
}四、总结与深入
动态规划（Dynamic Programming，简称DP）是一种解决复杂问题的方法，其核心思想是将问题分解成若干个子问题，通过解决子问题来解决原问题。DP的主要好处和用法如下：
1. 提供了一种解决复杂问题的有效方法：DP能够将复杂问题分解成多个简单的子问题，并通过求解子问题来得到原问题的解。这种分解与求解的方法可以大大简化问题的解决过程，减少复杂度。
2. 避免重复计算：DP在求解问题时通常会利用子问题的解来构建更大规模的问题的解。在这个过程中，DP会避免重复计算已经求解过的子问题，以提高效率。通过记忆化搜索或者构建动态规划表，可以有效地存储和重复利用已解决的子问题的结果。
3. 提高时间和空间效率：通过DP的分解和求解方法，往往可以将问题的复杂度从指数级别降低到多项式级别，从而大大减少了问题的求解时间。此外，通过存储已解决的子问题结果，可以减少额外的计算和存储空间的使用。
4. 适用范围广：DP不仅适用于求解优化问题，例如最长递增子序列、背包问题等，还适用于求解组合问题，例如排列组合、拆分问题等。因此，DP是一种非常通用且强大的问题求解方法。
综上所述，DP是一种将复杂问题分解为简单子问题并通过求解子问题来解决原问题的方法。它的好处包括提供了一种解决复杂问题的有效方法、避免重复计算、提高时间和空间效率，适用范围广等。为了使用DP解决问题，通常需要找到子问题的递推关系、设计状态转移方程，并采用记忆化搜索或者构建动态规划表的方法来存储和重复利用子问题的结果。
-----------------------------------------------------------结束----------------------------------------------------------------
励志就像给自己插上翅膀，才能飞得更高。————旺仔的编程小屋
