DP动态规划入门学习记录（一）

引入：金币

小招在玩一款游戏，在一个N层高的金字塔上，以金字塔顶为第一层，第i层有i个落点，每个落点有若干金币，在落点可以往向下或右斜向下移动，问能获得的最大金币值。

例：

5
8
3 8
8 1 0
4 7 5 4
3 5 2 6 5

局部最优解不一定是全局最优解

每一步会受到上一步决策的影响

动态规划：多阶段决策问题的最优解

1. 重叠子问题

2. 最优子结构

3. 无后效性

例题1：硬币问题

有3种面额的硬币（2、5、7元面额），需要硬币组合成i元，求需要的最小硬币数n

分析：

1.分析问题状态，f[i]表示组成i元所需最小硬币数

2.分解子问题（①从最后一步，②分析决策）$f[i]=min(f[i-2],f[i-5],f[i-7])+1$；状态定义：

​ 1）具备最优子结构（当前的最优解能够从之前阶段的最优解递推得到)

​ 2）无后效性（当前最优解一旦确定，便不会被后面阶段影响）

3.初始化状态数组和边界状态

4.思考计算顺序：从小到大

5.得到最终答案：ans=f[n];

#includeusing namespace std;int main(){int f[1000];memset(f,0x3f,sizeof(f));//初始化边界状态f[0]=0;//初始化边界状态int n;cin>>n;for(int i=1;i=7)f[i]=min(f[i-2],min(f[i-5],f[i-7]))+1;else if(i>=5)f[i]=min(f[i-5],f[i-2])+1;else if(i>=2)f[i]=f[i-2]+1;}cout<<f[n];return 0;}

tips:0x3f极大值 0x7f最大值 127极大值 128极小值

例题2：数字金字塔

题目描述

观察下面的数字金字塔。

写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。

 73   8     8   1   0   2   7   4   4 4   5   2   6   5 

在上面的样例中,从7→3→8→7→5 的路径产生了最大

输入格式

第一个行一个正整数r,表示行的数目。

后面每行为这个数字金字塔特定行包含的整数。

输出格式

单独的一行,包含那个可能得到的最大的和。

输入输出样例

输入 #1

573 88 1 02 7 4 44 5 2 6 5 

输出 #1

30

说明/提示

【数据范围】
对于 100% 的数据，1≤r≤1000，所有输入在 [0,100] 范围内。

递归写法（只有函数）：

int a[100][100];void tri(int x,int y,int len){    if(x==n)    { if(Max<len)     Max=len; return;    }    tri(x+1,y,len+a[x+1][y]);    tri(x+1,y+1,len+a[x+1][y+1]);}

问题是存在重复子问题

还是分析一下问题：

1.分析问题状态：

​ $f[x][y]$表示从（1，1）到（x，y）的最大路径长度

2.分解子问题

​ $f[x][y]=max(f[x-1][y-1],f[x-1][y])+a[x][y]$;

3.初始化状态数组金额边界状态

​ 1）初始化状态数组f为极小值-0x33f3f3f

​ 2）初始化边界状态$f[1][1]$为$a[1][1]$

4.思考计算顺序

​ 从上到下，从左到右

5.获得最终答案

​ $ans=max(f[n][k])$； $k\in [1,n]$

按照这个思路，写出代码：

#includeusing namespace std;int a[1000][1000];int f[1000][1000];int main(){    //初始化边界数组memset(f,-0x3f,sizeof(f));int r;cin>>r;for(int i=1;i<=r;i++){for(int j=1;j>a[i][j];}}f[1][1]=a[1][1];//初始化边界状态    //递推，从第二层开始for(int i=2;i<=r;i++){for(int j=1;j<=i;j++){f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j];}}    //求最终答案int Max=-0x3f;for(int i=1;iMax)Max=f[r][i];}cout<<Max;return 0;}

千万不要忘了，$f[i][j]$赋值后面要加上那个点本身的数字$a[i][j]$

但是，我又犯了一个致命的错误

我定义a和f数组的时候只定义了$a[1000][1000]和f[1000][1000]$

【数据范围】
对于 100% 的数据，1≤r≤1000，所有输入在 [0,100] 范围内。

看到了吧，数组定义时应该多定义一点，至少为$a[1001][1001]和f[1001][1001]$

进阶（逆向思维）

可以正着推，那么也就可以逆着推，试着从最后一排开始，往前直到第一排进行计算

也不难，一会就写出来了

#includeusing namespace std;int a[1005][1005];int f[1005][1005];int main(){memset(f,-0x3f,sizeof(f));//初始化边界数组int r;cin>>r;for(int i=1;i<=r;i++){for(int j=1;j>a[i][j];}}for(int i=1;i=1;i--){for(int j=1;j<=i;j++){f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j];}}    //输出最终答案cout<<f[1][1];return 0;}

例题3：动态规划-最长不下降子序列

在一个数字序列中，找到一个最长的子序列，使得这个子序列是不下降（非递减）的。

（5，-1）下降的，不符合

（1，3，4）符合的

输入：

81 2 3 -9 3 9 0 11

输出：

6

分析：

最先思考的时候把f[i]表示为子序列的长度，发现不行，于是进行更改

1.f[i]表示前i项以a[i]为结尾的子序列长度

2.分解子问题

​ $if(a[i]>a[k])f[i]=max(f[i],f[k]+1);k\in [1,i-1]$

3.初始化状态数组和边界状态

​ 1）初始化状态数组f为1

​ 2）初始化边界状态f[1]为1

4.思考计算顺序

​ 从小到大

5.获得最终答案

​ $ans=max(ans,f[k]);k\in [1,n]$

代码大概就是这样了：

#includeusing namespace std;int n;int a[1001];int f[1001]; int Max=0; int main(){cin>>n;for(int i=1;i>a[i];f[i]=1; }for(int i=2;i=1;j--){if(a[i]>=a[j])f[i]=max(f[i],f[j]+1);}}for(int i=1;i<=n;i++){Max=max(Max,f[i]);}cout<<Max;return 0;}

详细过程分析可另搜索

例题4：最大子段和

题目描述

给出一个长度为n的序列 a，选出其中连续且非空的一段使得这段和最大。

输入格式

第一行是一个整数，表示序列的长度 n。

第二行有 n个整数，第 i个整数表示序列的第 i个数字 $ai$。

输出格式

输出一行一个整数表示答案。

输入输出样例

输入 #1

72 -4 3 -1 2 -4 3

输出 #1

4

说明/提示

样例 1 解释

选取 [3, 5] 子段 {3, -1, 2}，其和为 4

数据规模与约定

• 对于 40% 的数据，保证 n*≤2×103 10^3 103。
• 对于 100% 的数据，保证 1≤n≤2×105 10^5 105，− 104 ≤ a   i ≤ 104 -10^4 ≤ a~i ≤ 10^4 −104≤a i≤104。

分析：

1.f[i]表示前i项以a[i]为结尾的所有区间的最大子段和

2.分解子问题

​ $f[i]=max(f[i-1]+a[i],a[i])$;

3.初始化状态数组和边界状态

​ 1）初始化状态数组f为极小值-0x3f3f3f

​ 2）初始化边界状态f[1]为a[1]

4.思考计算顺序

​ 从小到大

5.获得最终答案

​ $ans=max(ans,f[k]);k\in [1,n]$

代码：

#includeusing namespace std;int n;int a[200001];int f[200001];int Max=0;int main(){cin>>n;for(int i=1;i>a[i];f[i]=-0x3f3f3f3f;}f[1]=a[1];for(int i=2;i<=n;i++){f[i]=max(f[i-1]+a[i],a[i]);}for(int i=1;i<=n;i++)Max=max(Max,f[i]);cout<<Max;return 0;}

真的很费脑壳！！

2022.4.28