您现在的位置是：首页 >技术交流 >LeetCode[动态规划]746.使用最小花费爬楼梯+198.打家劫舍网站首页技术交流

746. 使用最小花费爬楼梯

题目：

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。

示例：

输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。- 支付 15 ，向上爬两个台阶，到达楼梯顶部。总花费为 15 。

思路： 

1.动态数组代表含义：dp[i] 代表到达第i个台阶花费的最小体力

2.确定递推公式:

        dp[i] = Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);

        dp[i-1]+cost[i-1]：表示上一次跳了一步到达i层；

        dp[i-2]+cost[i-2]：表示上一次跳了两步到达i层，每次取两者最小的，可求出最地的花费。

3.dp数组初始化：

        由于题目表述可以从下标为 0 或下标为 1 的台阶开始爬楼梯，因此在0或1下标下，不花费体力，初始值dp[0] =0, dp[1] = 0;

4.确定遍历顺序: 从前到后

5.举例推导dp数组：

cost = [1, 100, 1, 1, 1, 100, 1, 1, 100,1] 

dp  =   [0,  0,   1,  2, 2,  3   ,3, 4,   4,  5, 6]

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

 198. 打家劫舍

 题目描述：

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 ：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

 思路：

1.动态数组代表含义：dp[i] 代表 包含i之前的房屋获取的最高金额。

2.确定递推公式：

        dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);

        情况一，第i个不偷，最高金额可能为dp[i-1]；

        情况二，第i个偷，则第i-1个不偷，最高金额可能为dp[i-2]+nums[i]。

3.dp数组初始化：

        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]).

4.确定遍历顺序：

        从前到后.

5.举例推导dp数组：

         n = {2,7,9,3,1},

        dp = {2,7,11,11,12}。

class Solution {
    public int rob(int[] nums) {
        if (nums==null)return 0;
        if (nums.length==1)return nums[0];
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);
        for (int i = 2; i <nums.length; i++) {
            dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);
        }
        return dp[nums.length-1];
    }
}