第十四届蓝桥杯集训——练习解题阶段(无序阶段)-dp练习3
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-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]);
}
}
- 点赞
- 收藏
- 关注作者
评论（0）