最近的一些文章都可能会很碎,写到哪里是哪里,过一阵子会具体的整理一遍,这里其它的类型题先往后排一排,因为蓝桥最后考的也就是对题目逻辑的理解能力,也就是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]);
}
}