当前位置: 首页 > news >正文

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

搜索&动态规划

  • 前言
  • 砝码称重
    • 满分代码及思路
      • solution 1(动态规划)
      • solution 2(BFS)
  • 跳跃
    • 满分代码及思路
      • solution 1(动态规划)
      • solution 2 (BFS)
  • 积木画
    • 满分代码及思路
    • 动态规划思路讲解
      • solution

前言

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

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

砝码称重

在这里插入图片描述

题目链接

满分代码及思路

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;
} 

http://www.mrgr.cn/news/97481.html

相关文章:

  • 测开八股收集
  • 3D激光轮廓仪知识整理(待补充)
  • 代码随想录算法训练营第十一天
  • 2025-04-07 NO.3 Quest3 MR 配置
  • 《从零搭建Vue3项目实战》(AI辅助搭建Vue3+ElemntPlus后台管理项目)零基础入门系列第二篇:项目创建和初始化
  • RAG中构建个人知识库
  • Python高级爬虫之JS逆向+安卓逆向1.2节: 变量与对象
  • 从传递函数到PID控制器
  • C++20 统一容器擦除:std::erase 和 std::erase_if
  • nacos集群启动问题
  • 2025 年前端与后端开发方向的抉择与展望-优雅草卓伊凡
  • 【Vue】选项卡案例——NBA新闻
  • Linux学习笔记(1) 目录结构与路径描述:对比 Windows 系统差异(期末,期中复习笔记全)
  • 前缀和和差分笔记
  • 【JS】二分查找
  • 【Pandas】pandas DataFrame astype
  • 4月7日随笔
  • 内网文件传输新体验,聊天、传输、自定义,一应俱全
  • C++中常用的十大排序方法之4——希尔排序
  • Redlinux(2025.3.29)