每日算法-线性dp、递归

1.跳台阶拓展问题线性dp题目分析第一种解法线性dp根据线性dp的经验可以定义状态表示为dp[i]跳到i级台阶总共有多少总跳法因为一次青蛙可以跳任意级台阶所以跳到i级台阶的跳法就是先跳到0~i-1级台阶后再跳一步就可以跳到i级台阶。dp[i]dp[j]0ji-1。dp表里的值全部初始化为1因为可以一步跳到i级台阶。解法1的代码时间复杂度为On^2当数据量太大时就过不了了。第二种解法找规律当只有1级台阶时总跳法为1。当只有2级台阶时总跳法为2。先跳到1级台阶、再跳到2级直接跳到2级台阶当只有3级台阶时总跳法为4。跳到2级台阶有2种跳法跳到1级台阶有1种跳法还可以直接跳到3级台阶总共就是4种当只有4级台阶时总跳法为8。跟3级台阶的推导过程一样。。。。。。当只有n级台阶时总跳法为2的n-1次方。该方法的时间复杂度为o1空间复杂度也为o1。解法1代码class Solution { public: int jumpFloorII(int number) { vectorint dp(number,1); for(int i1;inumber;i) { for(int j0;ji-1;j) { dp[i]dp[j]; } } return dp[number-1]; } };解法2代码class Solution { public: int jumpFloorII(int number) { return 1(number-1); } };2.字符串的排列递归排列问题题目分析由题意可知这道题是个排列问题排列问题就是把每个位置的值排好就可以了而排每个位置的值又是一个重复问题所有这题用递归来解决。递归题最重要的就是把决策树画出来把不符合题意、重复结果的枝给剪掉。这道题的重复问题就是从s中挑一个字符排在要排的位置上递归出口是当pathn时把path加入ret中并返回。递归还有要注意的就是回溯恢复现场以及全部变量的使用不需要传参。①是第一个要剪枝的地方因为和左边那个树枝递归下去的结果是一样的会出现重复结果剪枝策略就是用一个bool hash[128]来记录字符有没有在当前递归层使用过。②是第二个要剪枝的地方因为根据题意一个字串不能重复使用用一个全局的bool hash[n]来记录字符有没有在上一递归层使用过别忘了递归结束恢复现场。代码class Solution { public: bool vis[11]{0}; string path; int n; vectorstring ret; string s; void dfs() { if(path.size()n) { ret.push_back(path); return; } bool check[128]{0}; for(int i0;in;i) { if(check[s[i]-a]||vis[i]) continue; paths[i]; vis[i]true; dfs(); path.pop_back(); vis[i]false; check[s[i]-a]true; } } vectorstring Permutation(string str) { sstr; nstr.size(); dfs(); return ret; } };3.kotori和迷宫bfs最短路题目分析这道题因为是求最短路径的问题所以用bfs来解决bfs可以保证第一次遍历到的出口是最近的。这道题借助一个和二维数组一样规模的dis数组来标记某个点是否已经遍历过已经到达某个点的最短距离。bfs难的不是理解题意而是编写代码。代码#includeiostream #includevector #includestring.h #includequeue #includestring using namespace std; int n,m; int dx[4]{0,0,-1,1}; int dy[4]{-1,1,0,0}; int dis[31][31]; void bfs(vectorstring map,int i,int j) { queuepairint,int q; q.push({i,j}); dis[i][j]0; while(!q.empty()) { auto [a,b]q.front(); q.pop(); for(int k0;k4;k) { int xdx[k]a,ydy[k]b; if(x0xny0ymdis[x][y]-1map[x][y]!*) { dis[x][y]dis[a][b]1; if(map[x][y]!e) { q.push({x,y}); } } } } } int main() { cinnm; vectorstring map(n); memset(dis,-1,sizeof dis); for(int i0;in;i) cinmap[i]; for(int i0;in;i) { for(int j0;jm;j) { if(map[i][j]k) { bfs(map,i,j); } } } int ret0; int tmp0x3f3f3f3f; for(int i0;in;i) { for(int j0;jm;j) { if(map[i][j]edis[i][j]!-1) { ret; tmpmin(tmp,dis[i][j]); } } } if(ret0) cout-1endl; else coutret tmpendl; return 0; }