【动态规划专项训练】基础篇

ฅ(๑˙o˙๑)ฅ 大家好, 欢迎大家光临我的博客：面向阿尼亚学习
算法学习笔记系列持续更新中~

---

---

前言

干翻动态规划问题

动态规划问题描述及思路

动态规划(Dynamic Programming)，无非就是利用历史记录，来避免我们的重复计算。而这些历史记录，我们得需要一些变量来保存，一般是用一维数组或者二维数组来保存。

算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法

第一步骤：定义数组元素的含义，上面说了，我们会用一个数组，来保存历史数组，假设用一维数组 dp[] 吧。这个时候有一个非常非常重要的点，就是规定你这个数组元素的含义，例如你的 dp[i] 是代表什么意思？

第二步骤：找出数组元素之间的关系式，我觉得动态规划，还是有一点类似于我们高中学习时的归纳法的，当我们要计算 dp[n] 时，是可以利用 dp[n-1]，dp[n-2]……dp[1]，来推出 dp[n] 的，也就是可以利用历史数据来推出新的元素值，所以我们要找出数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，这个就是他们的关系式了。而这一步，也是最难的一步

第三步骤：找出初始值。学过数学归纳法的都知道，虽然我们知道了数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，我们可以通过 dp[n-1] 和 dp[n-2] 来计算 dp[n]，但是，我们得知道初始值啊，例如一直推下去的话，会由 dp[3] = dp[2] + dp[1]。而 dp[2] 和 dp[1] 是不能再分解的了，所以我们必须要能够直接获得 dp[2] 和 dp[1] 的值，而这，就是所谓的初始值。

有了初始值，并且有了数组元素之间的关系式，那么我们就可以得到 dp[n] 的值了，而 dp[n] 的含义是由你来定义的，你想求什么，就定义它是什么**

以上可以看出：

动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。 ( 即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解 )

练几个题吧~！

1. 爬梯子

题目描述：

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

思路：

最基础的动态规划问题
1.首先我们来定义 dp[i] 的含义
dp[i]表示跳上一个 i 级的台阶总共有 dp[i] 种跳法。
2.状态转移方程
由于情况可以选择跳一级，也可以选择跳两级，所以青蛙到达第 n 级的台阶有两种方式
一种是从第 n-1 级跳上来
一种是从第 n-2 级跳上来
由于我们是要算所有可能的跳法的，所以有 dp[n] = dp[n-1] + dp[n-2]。
3.找出初始条件
当 n = 1 时，dp[1] = dp[0] + dp[-1]，而我们是数组是不允许下标为负数的，所以对于 dp[1]，我们必须要直接给出它的数值，相当于初始值，显然，dp[1] = 1。一样，dp[0] = 0.（因为 0 个台阶，那肯定是 0 种跳法了）。

AC代码及注释：

#include <iostream>
using namespace std;
int main()
{
    
	int n;
	cin>>n;
	int dp[n];
	//初始化 
	dp[0]=0;
	dp[1]=1;
	
	for(int i=2;i<=n;i++)
	{
    
		//状态转移方程 
		dp[i]=dp[i-1]+dp[i-2];
	}
	cout<<dp[n]<<endl;
	return 0;
}

2. 过河卒

过河卒

题目描述

思路：

卒只能向下或向右走，易得状态转移方程f(i,j)=f(i-1,j)+f(i,j-1)
为方便解题，给棋盘加1的偏移量，标记马可以走的位置为-1判断即可

AC代码及注释：

#include<iostream>
#include<algorithm>
using namespace std;
long long dp[30][30];
int mx[8]={
    -2,-2,-1,-1,1,1,2,2},my[8]={
    1,-1,2,-2,2,-2,1,-1};//马的偏移量 

int main(){
    
    int n,m,x,y;
    cin>>n>>m>>x>>y;
    n+=1;m+=1;x+=1;y+=1;//整体加一行一列，便于边界检查
    for(int i=0;i<8;i++){
    
        if(x+mx[i]>=1&&x+mx[i]<=n&&y+my[i]>=1&&y+my[i]<=m)
            dp[x+mx[i]][y+my[i]]=-1;//-1表示不能走 
    }
    dp[1][0]=1;//根据dp(1,1)=dp(0,1)+dp(1,0)
             //我们只需要让dp(0,1)=1或者dp(0,1)=1即可
    dp[x][y]=-1;//马所在的点也不能走
    for(int i=1;i<=n;i++){
    
        for(int j=1;j<=m;j++){
    
            if(dp[i][j]==-1)
                dp[i][j]=0;
            else{
    
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
    }

    cout<<dp[n][m];
    return 0;
}

3.砝码称重

砝码称重

题目描述：

思路：

f[i]表示 “重量 i 成立”
三重循环遍历找所有成立的

AC代码及注释：

#include <bits/stdc++.h>
using namespace std;
const int N=1001;
int a[7],w[7]={
    0,1,2,3,5,10,20},f[N];
//a数组存放的是每种砝码的数量，w数组是每种砝码的重量，f[i]表示 “重量 i 成立”
int main()
{
    
	for (int i=1;i<=6;i++)//输入
	{
    
		cin>>a[i];
	}
	f[0]=1;
	for (int i=1;i<=6;i++)//枚举六种砝码
	{
    
		for (int j=1;j<=a[i];j++)//枚举每个砝码
		{
    
			for (int k=1000;k>=0;k--)//寻找 已成立的重量
			{
    
			    if (f[k])//若此重量成立
				{
    
					f[k+w[i]]=1;//那么这个重量加上这个未使用的砝码的总重量也成立
				}
			}
		}
	}
	int ans=0;
	for (int i=1;i<=1000;i++)
	{
    
		if (f[i]) ans++;
	}
	cout<<"Total="<<ans<<endl;
	return 0;
 } 

4.2022

题目描述：

思路：

相比上一题，这个要求拆分成十个数字，还要等于2022，本题使用二维DP
dp[j][k]表示j个数相加等于k的方法个数
结果可能会很大，所以要开long long

AC代码及注释：

#include <iostream>
using namespace std;
typedef long long LL;

LL dp[11][2025];

int main()
{
    
	dp[0][0]=1;
	for(int i=1;i<=2022;i++)
	{
    
		for(int j=10;j>=1;j--)
			for(int k=1;k<=2022;k++)
				if(k>=i)//避免重复
				dp[j][k]+=dp[j-1][k-i];
		}
		cout<<dp[10][2022]<<endl;
}

5. 摘花生

摘花生

题目描述：

思路：

本题求最大的数字和
dp[i][j]表示到（i，j）位置的最大和
可以从左方以及上方下来，所以
状态转移方程为 dp[i][j] = max(dp[i][j-1] + a[i][j], dp[i-1][j] + a[i][j]);

AC代码及注释：

#include <iostream>
#include <cstring>
int a[1007][1007];
int dp[1007][1007];
using namespace std;

int main()
{
    
    
    int t;
    cin>>t;
    while(t--)
    {
    
        int n,m;
        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++)
            {
    
                dp[i][j]=max(dp[i-1][j]+a[i][j],dp[i][j-1]+a[i][j]);
            }
        }
        
        cout<<dp[n][m]<<endl;
    }
    return 0;
}

6. 数字三角形

数字三角形

题目描述：

思路：

本题求最大的数字和
dp[i][j]表示到（i，j）位置的最大和
可以从左上方以及上方下来，所以
状态转移方程为 dp[i][j] = max(dp[i-1][j-1] + a[i][j], dp[i-1][j] + a[i][j]);

AC代码及注释：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, INF = 1e9;

int n;
int a[N][N], dp[N][N];

int main() {
    
    cin >> n;
    //输入
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= i; j++) 
          cin>>a[i][j];
    //初始化
    for (int i = 0; i <= n; i++) 
        for (int j = 0; j <= i + 1; j++) // 每行需要多初始化一个，考虑到两边
            dp[i][j] = -INF;
    dp[1][1] = a[1][1];
    
    for (int i = 2; i <= n; i++) // 若从1开始，结果为负无穷，由前状态转移而来
        for (int j = 1; j <= i; j++) // 从2开始才有前状态
            dp[i][j] = max(dp[i-1][j-1] + a[i][j], dp[i-1][j] + a[i][j]);//状态转移方程
        
    int res = -INF;
    for (int i = 1; i <= n; i++) res = max(res, dp[n][i]);//在最下一行取最大
        
    cout << res << endl;
    
    return 0;
}

也可以从下往上进行dp，不用考虑边界

#include<bits/stdc++.h>
using namespace std;

const int N=510;
int dp[N][N];
int n;

int main(){
    
    cin>>n;
    for(int i=1;i<=n;i++){
    
        for(int j=1;j<=i;j++){
    
            cin>>dp[i][j];
        }
    }

    for(int i=n;i>=1;i--){
    
        for(int j=i;j>=1;j--){
    
            dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+dp[i][j];
        }
    }
    cout<<dp[1][1]<<endl;
}

---

最后