:-: 9.2 使用最小花费爬楼梯 * * * * * **题干：** 数组的每个索引做为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 cost[i] (索引从0开始)。每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。 示例 1: ~~~ 输入: cost = [10, 15, 20] 输出: 15 解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。 ~~~ 示例 2: ~~~ 输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 输出: 6 解释: 最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。 ~~~ 注意： ~~~ cost 的长度将会在 [2, 1000]。 每一个 cost[i] 将会是一个Integer类型，范围为 [0, 999]。 ~~~ **题目分析：** 首先分析题干，题目的注意事项，假设数组b是存储值数组，a数组是原数组，首先 你可以选择从索引为 0 或 1 的元素作为初始阶梯 这句话分析得 b[0] = a[0],b[1] = a[1] ,接着分析数组a有最少的元素的时候为两个元素的时候： f(2) = Math.min(b[0],b[1]); 然后分析数组a有三个元素的时候： f(3) = Math.min(b[0]+a[2],b[1]+a[2]) = f(2)+a[2]; 比如数组a为 [10,15,20]，通过我们的大脑肯定一眼看出，答案为15，但是计算机需要有严谨的计算步骤才能做出判断:（Math.min(10 + 20, 15 + 20)）= 30，此时数组b,为[10,15,30],我们还缺少一步，这个仅仅是b[0],b[1]做了对比就加a[2]，我们实际上对比应该是b[i] 和 b[i+1] = Math.min(b[i - 2],b[i - 1]) +a[i]做对比，因此我们得到我们的动态规划方程： dp[i] = Math.min(dp[i - 1], dp[i - 2]) + costCurrent。 **新手有可能遇到的解题思路陷阱：** 忽略计算机判断的步骤，或者没有这个意识，人脑也要做判断，只不过我们可能忽略这个步骤。 **解题思路分析以及代码实现：** 第一种思路：数组存储法 第一种思路代码： ~~~ public static int minCostClimbingStairs(int[] cost) { int[] dp = new int[cost.length]; dp[0] = cost[0];//两个起点 dp[1] = cost[1]; for(int i = 2; i < cost.length; i++) { int costCurrent = cost[i]; dp[i] = Math.min(dp[i - 1], dp[i - 2]) + costCurrent; } return Math.min(dp[cost.length - 1],dp[cost.length-2]); } ~~~ **复杂度分析：** 时间复杂度：O(n)。 空间复杂度：O(n)。 第二种思路：看了第一种思路的代码，有没有发现有一些相同的地方，或者我们没考虑到的地方，或者更加巧妙的地方呢？观察：return Math.min(dp[cost.length - 1],dp[cost.length-2]) 和dp[i] = Math.min(dp[i - 1], dp[i - 2]) + costCurrent有什么不同呢？它们区别除了 + costCurrent 也没什么区别，我们何不来统一一下，使得结构巧妙一些。 第二种思路代码： ~~~ public int minCostClimbingStairs(int[] cost) { int[] dp = new int[cost.length + 1]; dp[0] = cost[0]; dp[1] = cost[1]; for(int i = 2; i <= cost.length; i++) { int costCurrent = i == cost.length ? 0 : cost[i]; dp[i] = Math.min(dp[i - 1], dp[i - 2]) + costCurrent; } return dp[cost.length]; } ~~~ **复杂度分析：** 时间复杂度：O(n)。 空间复杂度：O(n)。 第三种思路：迭代法，为了优化我们的算法，我们再思考一下看看复杂度还有什么可以优化的地方，我们发现我们可以优化空间复杂度，我们发现每一次迭代的过程中我们只要使用前两个的状态就可以得到新的状态，所以我们完全没有必要把所有状态值全部保留下来，每次保留所求状态的前两个状态就可以，所以空间复杂度就降低到O(1)。 第三种思路代码： ~~~ public static int minCostClimbingStairs(int[] cost) { int sum = 0,sum1 = cost[0],sum2 = cost[1]; for(int i = 2; i <= cost.length; i++) { int costCurrent = i == cost.length ? 0 : cost[i]; sum = Math.min(sum1, sum2) + costCurrent; sum1 = sum2; sum2 = sum; } return sum; } ~~~ **复杂度分析：** 时间复杂度：O(n)。 空间复杂度：O(1)。 **若有理解错误的、写错的地方、更好的思路，方法，望各位读者评论或者发邮件指正或指点我，不胜感激。**