企业官网建设流程全解析

必应搜索引擎网站,安徽网站优化好不好,wordpress比价插件,公司宣传彩页设计模板目录 前言 在动态规划中#xff1a; 在bfs中#xff1a; 前言 对于普通的路线问题#xff0c;我们可以存储全局变量path存储路线过程中的#xff0c;一个个“点”。由于这些点就是按照顺序存储的#xff0c;路线就是可以直接得到的。 但是如果是动态规划#xff0c;…目录前言在动态规划中在bfs中前言对于普通的路线问题我们可以存储全局变量path存储路线过程中的一个个“点”。由于这些点就是按照顺序存储的路线就是可以直接得到的。但是如果是动态规划或者是带有图需要从一个点开始找到另一个点我们在找到结果后还需要回溯这个结果的实现路线这里没办法轻松得到路线那么我们就需要尽可能利用条件从该结果往回退找到上一个节点是什么这里介绍两种目前已经遇到的情景。在动态规划中以牛客网 最长公共子序列II 为例最长公共子序列(二)_牛客题霸_牛客网找到最长子序列我们还需要返回这个子序列是什么既然我们已经完成填表那么我们就可以以dp值为引按照dp值递减的顺序修改i和j的坐标当s1[i]s2[j]时此时这个就是我们要寻找的节点头插进结果让i--j--意味着继续道s1[0,i-1],s2[0,j-2]区间内寻找如果不等往可以使dp值减少的方向前进于是我们就找到了路线。代码实现如下class Solution { public: string LCS(string s1, string s2) { int ns1.length(),ms2.size(); s1 s1,s2 s2; vectorvectorint dp(n1,vectorint(m1)); for(int i1;in;i) { for(int j1;jm;j) { if(s1[i]s2[j])dp[i][j]dp[i-1][j-1]1; else dp[i][j]max(dp[i-1][j],dp[i][j-1]); } } //回溯构造LCS string ret; int in,jm; while(ij) { if(s1[i]s2[j]) { rets1[i]ret; --i; --j; } else if(dp[i-1][j]dp[i][j-1])--i; else --j; } return ret?-1:ret; } };在bfs中以bjfuoj的 码码我迷路了 为例BJFUOJ | 码码我迷路了该题是一道很简单的bfs经典题但找到目标点后我们还需要输出从起点到目标点依次经过的路径此时依旧利用回溯构造路线。回溯路线因为我们需要从一个节点得到上一个节点的信息这里节点的信息就是对应的坐标那么我们可以创建一个“point”类型的二维数组fa,用fa[i][j]存储到达点{i,j}的上一个节点的坐标具体代码体现就是在bfs中队列push新节点的时候我们得到的节点假设是{newx,newy}因为newx和newy是由{x,y}得到的我们使fa[newx][newy]{x,y}这样就得到了上一个节点的位置就可以实现回溯了。此篇完。