第十四届蓝桥杯集训——练习解题阶段(无序阶段)-dp练习3
前言
最近的一些文章都可能会很碎，写到哪里是哪里，过一阵子会具体的整理一遍，这里其它的类型题先往后排一排，因为蓝桥最后考的也就是对题目逻辑的理解能力，也就是dp分析能力了，所以就主要目标定在这里，最近的题目会很散，很多，基本上都是网罗全网的一些dp练习题进行二次训练，准备比赛的学生底子薄的先不建议看啊，当然，脑子快的例外，可以直接跳过之前的一切直接来看即可，只需要你在高中的时候数学成绩还可以那就没啥问题，其实，dp就是规律总结，我们只需要推导出对应题目的数学规律就可以直接操作，可能是一维数组，也可能是二维数组，总体来看二维数组的较多，但是如果能降为的话建议降为，因为如果降为起来你看看时间复杂度就知道咋回事了，那么在这里祝大家能无序的各种看明白，争取能帮助到大家。
题目描述：最小花费爬楼梯
/**
* 给定一个整数数组 cost ，其中 cost[i] 是从楼梯第i
* 个台阶向上爬需要支付的费用，下标从0开始。 一旦你支付此费用，
* 即可选择向上爬一个或者两个台阶。
* 你可以选择从下标为0或下标为1
* 的台阶开始爬楼梯。 请你计算并返回达到楼梯顶部的最低花费。
* 数据范围：数组长度满足1<=n<=10^5 ，
* 数组中的值满足1<=costi<=10^4
*
* @param args
*/
测试数据：
输入样式：
2,5,20
输出样式：
5
题解：
这里我直接带入数组了，使用了两种方法可以直接的在下列代码中看到。
这个规律在题目中说的就很明白了，这种基础练习的小题我们先多做一些，练习一下我们的dp反应速度，基础好了后面就是随机应变了，况且我们还能背一些常用规律的公示，特别是常出的最大公共子串啥的类型题目。
package com.item.action; public class Demo1 { /** * 给定一个整数数组 cost ，其中 cost[i] 是从楼梯第i<br/> * 个台阶向上爬需要支付的费用，下标从0开始。 一旦你支付此费用，<br/> * 即可选择向上爬一个或者两个台阶。 <br/> * 你可以选择从下标为0或下标为1<br/> * 的台阶开始爬楼梯。 请你计算并返回达到楼梯顶部的最低花费。 <br/> * 数据范围：数组长度满足1<=n<=10^5 ，<br/> * 数组中的值满足1<=costi<=10^4<br/> * * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int[] cost = { 2, 5, 20 }; /** * 测试数据 {2,5,20};<br/> * 将从下标为1的台阶开始，支付5 ，向上爬两个台阶，到达楼梯顶部。总花费为5 */ int minCostClimbingStairs_1 = minCostClimbingStairs_1(cost); System.out.println(minCostClimbingStairs_1); int minCostClimbingStairs_2 = minCostClimbingStairs_2(cost); System.out.println(minCostClimbingStairs_2); } /** * 解法1、 * * @param cost * @return */ public static int minCostClimbingStairs_1(int[] cost) { // 只有1层直接返回就行了免得出现越界 if (cost.length == 1) { return cost[0]; } //一步两步 int dp0 = cost[0]; int dp1 = cost[1]; //0/1都赋值了，从2开始 for (int i = 2; i < cost.length; ++i) { //第三方改值 int tmp = dp1; dp1 = Math.min(cost[i] + dp0, cost[i] + dp1); dp0 = tmp; } return dp0 > dp1 ? dp1 : dp0; } public static int minCostClimbingStairs_2(int[] cost) { if (cost.length == 1) { return cost[0]; } int dp[] = new int[cost.length]; dp[0] = cost[0]; dp[1] = cost[1]; for (int i = 2; i < cost.length; ++i) { //替换值 dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i]; } // 返回最小值即可 return Math.min(dp[dp.length - 1], dp[dp.length - 2]); } }
