从搜索丝滑过渡到动态规划的学习指南

前言

本文主要是通过一些竞赛真题 通过搜索和动态规划这两个角度 对比地去思考和解决这类令人头大的问题

我真的总感觉 并且这种感觉真的是越来越强烈 搜索我们总是正方向的去搜下一个满足需求的位置
而动态规划 我们总是去看 当前位置或者状态 能通过什么方式来走到 （状态转移） 而且往往需要取最优 这是一个逆向的过程 而且往往逆向是比较难的 所以我一开始连解析都看不懂 但是你一旦理解了这个思考方式 就会轻松很多很多

砝码称重

题目链接

满分代码及思路

solution 1（动态规划）

#include <bits/stdc++.h>
using namespace std;
const int N=110;
const int M=1e5+10;
//1首先明确状态和选择
//这题中状态就是重量和可用的砝码 选择就是放还是不放
//2.明确dp数组的定义
//dp[i][j]的定义就是对于前i个砝码是否能凑出来j的重量
//dp[3][2]=1 那意味着 对于前3个砝码能凑出2
//3.根据选择 写出状态转移方程
//放
//dp[i][j]=dp[i-1][j-wt[i]](因为是天平所以也有可能是加上当前重量)
//根据定义来理解就是 对于前i-1个砝码能凑出j-w[i]的重量 那么对于前i个砝码必定能凑出j的重量
//不放
//dp[i][j]=dp[i][j-1];
bool dp[N][M];
int n,m;
int wt[N];
int cnt=0;
int dynamic()
{for(int i=1;i<=n;i++){for(int j=0;j<=m;j++){dp[i][j]=dp[i-1][j]+dp[i-1][abs(j-wt[i])]+dp[i-1][j+wt[i]];//分别对应不放 放左边 放右边}}for(int i=1;i<=m;i++)//枚举所有重量{if(dp[n][i])//如果对于前n个砝码能凑出来i的重量 {cnt++;}}return cnt;
}
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>wt[i];m+=wt[i];//}memset(dp,0,sizeof(dp));dp[0][0]=1;//basecase 对于前0个砝码能凑出0的重量int res=dynamic();cout<<res<<endl;return 0;
}

solution 2（BFS）

#include<iostream>
#include<queue>
#include<cmath>
using namespace std;
queue<int> q;
const int N = 1e5+10;
bool sign[N];
int n,key;
int main()
{cin>>n;q.push(0);int ans = 0;for(int i=0; i<n; i++){cin>>key;queue<int> q2;while(!q.empty())//以q队列来加入，因为对每个key都进行q.front()+key和//abs(q.front()-key)进行筛选，所以不用管左边和右边是否有重复的砝码{if(!sign[q.front()+key])//这种情况相当于砝码全部放到右边{q2.push(q.front()+key);//如q2的队列sign[q.front()+key] = true;}if(!sign[abs(q.front()-key)])//左边和右边都放砝码{q2.push(abs(q.front()-key));sign[abs(q.front()-key)] = true;}q2.push(q.front());//把q.front()入到q2的队列，以便保存数据q.pop();//q出队}q = q2;//将q2赋值给q，保存数据}while(!q.empty()){if(q.front()>0) ans++;//因为q第一个入队的是0，但0又不算，所以把0排除在外q.pop();}cout<<ans;return 0;
}

跳跃

满分代码及思路

solution 1(动态规划)

#include <bits/stdc++.h>
using namespace std;
const int N=110;
int n,m;
int dp[N+1][N+1];
int val[N][N];
int dx[9]={-1,-2,-3,0,0,0,-1,-1,-2};
int dy[9]={0,0,0,-1,-2,-3,-1,-2,-1};
//其实我最开始想使用bfs来写 感觉比较容易想到 因为这题数据范围不算大而且只有一个测试点
//**********************************************************
//1 首先这题中的状态和选择是什么？
//状态就是 权值以及位置 选择就是走的方向//2 我们怎样定义DP数组？
//可以定义为 从（1,1）走到第（i,j）时的最大权值 //3 最后 我们怎么样根据选择写出状态转移方程
//我们无非就是九种选择对应九种方向 我们只需要把每种选择取最优就好
//所以总的来说 我们只需要不断计算 当下一个位置的权值会使选择之前的权值变大的时候 再更新dp数组就好
//即 dp[i][j]=dp[i+dx[k]][j+dy[k]]+val[i][j];int dynamic()
{//根据basecase以及返回值确定遍历的顺序for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){for(int k=0;k<9;k++){if(i+dx[k]>=1 && j+dy[k]>=1)//边界检查一下{if(dp[i][j]<dp[i+dx[k]][j+dy[k]]+val[i][j]){dp[i][j]=dp[i+dx[k]][j+dy[k]]+val[i][j];}}}}}return dp[n][m];
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>val[i][j];}}memset(dp,0,sizeof(dp));//basecasedp[1][1]=val[1][1];int res=dynamic();cout<<res<<endl;return 0;
}

solution 2 (BFS)

#include <stdio.h>
#include <stdlib.h>int a[100][100];   //数据数组
int state[100][100] = { 0 };  //表示每一个坐标是否走过
int m, n;          //方格图大小
int newsum;        //每走一步刷新权重
int max = 0;       //记录每次走到终点时权重最大值
int next[10][2] = {   /* A */{0,1},{0,2},{0,3},{1,0},{1,1},{1,2},{2,0},{2,1},{2,2},{3,0} };             // 每次只能走3格距离，在网格中排列如上,A为每一步起始点void dfs(int x, int y) {int x1, y1;    // 每走一步新的坐标if (x == m - 1 && y == n - 1) {  //由于不断往下搜索，将超出边界的移动都舍弃了，最终一定会到达mn终点，记录下此时的权重max = max > newsum ? max : newsum;return;    //仅仅为一条路，回到上一步，走没走过的路}for (int k = 0; k <= 9; k++) {  //循环遍历当前坐标下下一次运动的新坐标x1 = x + next[k][0];y1 = y + next[k][1];if (x1 >= m || y1 >= n) continue;  //超出边界，舍弃if (state[x1][y1] == 0) {      //未超边界且没有经过该点，从该点出发，走过该点state[x1][y1] = 1;         newsum = newsum + a[x1][y1];  dfs(x1, y1);               // 则该点继续往下搜索state[x1][y1] = 0;  newsum -= a[x1][y1];       // 回到没走过这个点的状态，更新state以及newsum}}return;
}int main()
{scanf("%d %d", &m, &n);for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++)scanf("%d", &a[i][j]);}newsum += a[0][0];max = newsum;state[0][0] = 1;      //数据初始化，相当于将小蓝放在(0,0)位置dfs(0, 0);        printf("%d", max);return 0;
}

积木画

满分代码及思路

动态规划思路讲解

好 首先我们需要分成三步

• 1.在这题中 回答我什么是状态 什么是选择
• 回顾之前我写的文章 状态是不是就是会改变的量 选择是不是影响状态改变的量
• 但是我们好像直接地认为 状态就是剩余的格子 选择就是选择哪种积木来摆 这是不太妥当的 因为 这样我试了一下不仅我们自己都不知道这个dp数组的含义是什么 更不要说写状态转移方程了
• 所以我们需要在考虑一下 怎样是合适的

我们可以这样想，一个积木放上去后，可能会出现三种情况：第一行比第二行多出一个积木；两行积木数相等；第二行比第一行多出一个积木。

这时候有同学可能会问：为什么最多就多出一个积木呢？

因为最后的答案一定是两行积木数相等，如果两行差的多了，就不能用 L 型积木填补。只用 I 型积木填补的话，只能横着填补，我们完全可以在之前相差不超过 1 时就用 I 型积木横着填补。

因为这个画布最多只有两行 所以这时 我们就可以知道 状态就是 两行的情况 是相等还是第一行多或者第二行多
选择就是 我们如果去选取积木以及摆法 是横着还是竖着还是旋转一下

• 2. 我们如何去定义这个dp数组
• 首先我们可以给我们上述的每个状态标一个号 方便表示
• 1：前 i 列拼完后，两行积木数量相等；
  0：前 i 列拼完后，第一行比第二行多 1 个积木块；
  2：前 i 列拼完后，第二行比第一行多 1 个积木块。
• 比如说 dp[2][1]=5它是啥意思 我们可以通过上面的分析 大致的描述出来
• 也就是前2列处理完后 在两行数量相等的状态下 拼满画布的方案总数
• 进而我们可以去 得知dp数组的定义

dp[i][j] 表示：处理到画布第 i 列时，处于 j 状态（两行数量关系）下，拼满画布前 i 列的不同方式的数量。最终要求的答案是 dp[N][1]，即拼满 2×N 画布且两行积木数量相等的方案数。

• 3 根据选择写出状态转移方程

初始化（basecase）
当没有列（i=0）时，积木都没放，自然两行相等，所以 f[0][1] = 1。

思考：我们已经有了basecase而且知道我们需要的答案是啥
那么我们是不是就可以去确定一下遍历的顺序 即从 1遍历到n 枚举每一列的情况

推导 f[i][1]（两行相等）：

放两个横 I 型：占两列，所以从 i-2 列的相等状态转移，即 f[i-2][1]。
放一个竖 I 型：占一列，从 i-1 列的相等状态转移，即 f[i-1][1]。
放 L 型（第一行方向）：比如在第 i 和 i-1 列拼 L 型，拼之前第二行多 1 个（f[i-1][2]）。
放 L 型（第二行方向）：拼之前第一行多 1 个（f[i-1][0]）。

最终：f[i][1] = [f[i-2][1] + f[i-1][1] + f[i-1][0] + f[i-1][2]] % 1000000007。

推导 f[i][0]（第一行多 1 个）：

放横 I 型在第一行：填补后，之前是第二行多 1 个（f[i-1][2]）。
放 L 型：和前一列组合，拼之前两行相等（f[i-2][1]）。

最终：f[i][0] = [f[i-1][2] + f[i-2][1]] % 1000000007。

推导 f[i][2]（第二行多 1 个）：

和 f[i][0] 对称：f[i][2] = [f[i-1][0] + f[i-2][1]] % 1000000007。

精髓 ：总的方案数=所有子问题的方案数之和 希望你能理解这句话

我自己一开始想用动态规划写 其实是很难想的 代码现在看来确实很短 但真的是短小精悍 凝结了很多思考在里面 上面的大部分都是对 洛谷大佬的原文 的进一步完善和补充 希望能帮大家减少一下理解的成本和门槛！！！

solution

#include <bits/stdc++.h>
using namespace std;
const int N=1e7+10;
#define MOD 1000000007
int dp[N][3];//1代表相等 0代表第一行多 2代表第二行多
int n;
int main()
{cin>>n;memset(dp,0,sizeof(dp));//basecase dp[0][1]=1;//第0列没有积木 所以可以理解为摆满的情况有1种for(int i=1;i<=n;i++)//枚举所有列{//我们能从什么状态转移到现在第一行多？无非就是之前i-1列第二行多 但是我们在第一行横着插入了I型积木 所以导致了现在第一行多的状态 //还有就是 原来i-2列是 相等的状态 现在我们倒着插入了 L型积木 也会导致 第一行多  同理我们写出dp[i][2]的状态转移方程dp[i][0]=(dp[i-1][2]+dp[i-2][1])%MOD;dp[i][2]=(dp[i-1][0]+dp[i-2][1])%MOD;//难点就是相等的情况是由什么状态转移而来的 这是关键也是我们需要考虑的 它之前可能相等 可能不相等dp[i][1]=((dp[i-1][1]+dp[i-2][1])%MOD+(dp[i-1][0]+dp[i-1][2])%MOD)%MOD;//为了防止在计算中间就爆int 我们分布取模//(a + b + c + d) % mod = ((a + b) % mod + (c + d) % mod) % mod }cout<<dp[n][1]<<endl;return 0;
}