第十四届蓝桥杯集训——练习解题阶段(无序阶段)-dp练习
最近的一些文章都可能会很碎,写到哪里是哪里,过一阵子会具体的整理一遍,这里其它的类型题先往后排一排,因为蓝桥最后考的也就是对题目逻辑的理解能力,也就是dp分析能力了,所以就主要目标定在这里,最近的题目会很散,很多,基本上都是网罗全网的一些dp练习题进行二次训练,准备比赛的学生底子薄的先不建议看啊,当然,脑子快的例外,可以直接跳过之前的一切直接来看即可,只需要你在高中的时候数学成绩还可以那就没啥问题,其实,dp就是规律总结,我们只需要推导出对应题目的数学规律就可以直接操作,可能是一维数组,也可能是二维数组,总体来看二维数组的较多,但是如果能降为的话建议降为,因为如果降为起来你看看时间复杂度就知道咋回事了,那么在这里祝大家能无序的各种看明白,争取能帮助到大家。
最最最最最基础的dp练习题,还是斐波那契数列,这里使用的是数组来完成的,我们来看一下示例:
package com.item.action;
public class Demo2 {
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(fun(10));
}
private static long fun(int n) {
// TODO Auto-generated method stub
int[] dp = new int[n];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i < n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n-1];
}
}
结果肯定是没有错误。
因为这个题目的规律我们都知道,所以那这个用作示例好理解一些:
看数的输出顺序是:【1,1,2,3,5,8,13,21,34,55】
规律是前两项之和等于第三项,这里我们使用了一维数组进行dp的操作,数据的规律我们可以直接用数学来表示:
dp[2]=dp[1]+dp[0]
这就是2、1、0呗,很明显规律的从2开始向前计算,前两个值直接下标减一即可,我们就能根据fori这个遍历总结规律了:
dp[i]=dp[i-1]+dp[i-2]
规律一下就有了,那么,我们根据规律直接输出表达式就可以完成我们最基础的dp题目分析了。
是不是so esay。我想是的,只要找到规律,这类题其实非常的好搞,但是规律总结才是最最最难的。需要使用我们灵活的脑瓜来逐一去剖析题目。
后面我们就会慢慢的开始一点点对题目进行解剖,希望大家对dp的理解能慢慢的深入。