第十四届蓝桥杯集训——练习解题阶段(无序阶段)-dp练习

第十四届蓝桥杯集训——练习解题阶段(无序阶段)-dp练习

前言

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