动态规划入门题目-＞使用最小费用爬楼梯

用户11305962

发布于 2024-10-09 15:57:45

850

发布于 2024-10-09 15:57:45

文章被收录于专栏：学习

1.题目：

2.解析：

做题模式：

步骤一：找状态转移方程

步骤二：初始化

步三：填表

步骤四：返回-> dp[n]

dp[i]表示到达 i 位置最小花费

逻辑：要爬到楼顶先找到 i 位置，

要找到 i 位置先找到 i-1,和 i-2位置

总结：状态转移方程dp[i] = Math.min (dp[i-1] + cos[i-1], dp[i-2] + cost[i-2])

代码：

public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n+1];
        for(int i = 2; i <= n; i++){
            dp[i] = Math.min(dp[i-1] + cost[i-1],dp[i-2] + cost[i-2]); 
        }

        return dp[n];
    }

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-09-27，如有侵权请联系 cloudcommunity@tencent.com 删除