电脑制作网站用哪个软件,建设新北川网站,c++培训,找做牙工作上哪个网站文章目录 前言LeetCode、746. 使用最小花费爬楼梯【简单#xff0c;动态规划 线性DP】题目与分类思路 资料获取 前言
博主介绍#xff1a;✌目前全网粉丝2W#xff0c;csdn博客专家、Java领域优质创作者#xff0c;博客之星、阿里云平台优质作者、专注于Java后端技术领域。… 文章目录 前言LeetCode、746. 使用最小花费爬楼梯【简单动态规划 线性DP】题目与分类思路 资料获取 前言
博主介绍✌目前全网粉丝2Wcsdn博客专家、Java领域优质创作者博客之星、阿里云平台优质作者、专注于Java后端技术领域。
涵盖技术内容Java后端、算法、分布式微服务、中间件、前端、运维、ROS等。
博主所有博客文件目录索引博客目录索引(持续更新)
视频平台b站-Coder长路 LeetCode、746. 使用最小花费爬楼梯【简单动态规划 线性DP】
题目与分类
题目链接LeetCode、746. 使用最小花费爬楼梯【简单动态规划 线性DP】
题目类型动态规划/线性DP一维DP 思路
思路描述我们可以使用一个dp数组第i个位置保存当前最耗费最小的费用接着初始化第0、1个台阶值对于之后的台阶位置我们都可以使用一个递推方程d
p(i) Math.min(dp(i - 1), dp(i - 2)) cost[i]最终返回顶部位置也就是dp[n]即可就是最小花费答案。
复杂度分析时间复杂度O(n)空间复杂度O(n)
class Solution {//1000个空间//dp(i) Math.min(dp(i - 1), dp(i - 2)) cost[i]public int minCostClimbingStairs(int[] cost) {int n cost.length;//定义dp数组int[] dp new int[n 1];//初始下标0、1位置dp[0] cost[0];dp[1] cost[1];//递推方程for (int i 2; i n; i ) {dp[i] Math.min(dp[i - 1], dp[i - 2]) (i n ? cost[i] : 0);}return dp[n];}
}资料获取
大家点赞、收藏、关注、评论啦~
精彩专栏推荐订阅在下方专栏
长路-文章目录汇总算法、后端Java、前端、运维技术导航博主所有博客导航索引汇总开源项目Studio-Vue—校园工作室管理系统(含前后台SpringBootVue)博主个人独立项目包含详细部署上线视频已开源学习与生活-专栏可以了解博主的学习历程算法专栏算法收录
更多博客与资料可查看获取联系方式文末获取开发资源及更多资源博客获取
