广州站扩建,建设大型网站制作品牌,做网站时如何给文字做超链接,wordpress搜索框作者简介#xff1a;大家好#xff0c;我是未央#xff1b; 博客首页#xff1a;未央.303 系列专栏#xff1a;牛客面试必刷TOP101 每日一句#xff1a;人的一生#xff0c;可以有所作为的时机只有一次#xff0c;那就是现在#xff01;#xff01;#xff01;… 作者简介大家好我是未央 博客首页未央.303 系列专栏牛客面试必刷TOP101 每日一句人的一生可以有所作为的时机只有一次那就是现在 文章目录
前言
一、跳台阶
题目描述
题目解析
二、不同路径的数目(一)
题目描述
题目解析
总结 前言
一、跳台阶
题目描述 描述一只青蛙一次可以跳上1级台阶也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法先后次序不同算不同的结果。 数据范围1≤n≤40 要求时间复杂度O(n) 空间复杂度 O(1)。 示例1 示例2 题目解析 解题思路 假设f[i]表示在第i个台阶上可能的方法数。逆向思维。如果我从第n个台阶进行下台阶下一步有2中可能一种走到第n-1个台阶一种是走到第n-2个台阶。 所以f[n] f[n-1] f[n-2]. 那么初始条件了f[0] f[1] 1。 所以就变成了f[n] f[n-1] f[n-2], 初始值f[0]1, f[1]1目标求f[n] 。 和斐波那契数列的模式一样。 代码解析 二、不同路径的数目(一)
题目描述 描述 一个机器人在m×n大小的地图的左上角起点。 机器人每次可以向下或向右移动。机器人要到达地图的右下角终点。 可以有多少种不同的路径从起点走到终点 备注m和n小于等于100,并保证计算结果在int范围内 数据范围0n,m≤100保证计算结果在32位整型范围内 要求空间复杂度 O(nm)时间复杂度 O(nm) 进阶空间复杂度 O(1)时间复杂度O(min(n,m)) 示例1 示例2 题目解析 解题思路 首先我们在左上角第一个格子的时候有两种行走方式如果向右走相当于后面在一个(n−1)∗m的矩阵中查找从左上角到右下角的不同路径数而如果向下走相当于后面在一个n∗(m−1)的矩阵中查找从左上角到右下角不同的路径数。 而(n−1)∗m的矩阵与n∗(m−1)的矩阵都是n∗m矩阵的子问题因此可以使用递归。 解题步骤: step 1终止条件 当矩阵边长n减少到1的时候很明显只能往下走没有别的选择了只有1条路径同理m减少到1时也是如此。因此此时返回数量为1.step 2返回值 对于每一级都将其两个子问题返回的结果相加返回给上一级。step 3本级任务 每一级都有向下或者向右两种路径选择分别进入相应分支的子问题。 代码解析 总结
