蓝桥杯2022年第十三届决赛真题-斐波那契数组(动态规划)

题目描述

如果数组 A = (a0, a1, · · · , an−1) 满足以下条件,就说它是一个斐波那契数组:

  1. n ≥ 2;

  2. a0 = a1;

  3. 对于所有的 i(i ≥ 2),都满足 ai = ai−1 + ai−2。

现在,给出一个数组 A ,你可以执行任意次修改,每次修改将数组中的某个位置的元素修改为一个大于 0 的整数。请问最少修改几个元素之后,数组 A 会变成一个斐波那契数组。

输入格式

输入的第一行包含一个整数 n ,表示数组 A 中的元素个数。

第二行包含 n 个整数 a0, a1, · · · , an−1,相邻两个整数之间用一个空格分隔。

输出格式

输出一行包含一个整数表示最少需要修改数组 A 中的几个元素之后,数组 A 可以变为一个斐波那契数组。

样例输入

3
4 6 9

样例输出

4

解答

  1. 这道题是典型的斐波那契数列题,而且因为题目的数据范围很大,使用暴力递归几乎全部数据都会超时,所以我们使用动态规划进行解答
  2. 写出基本的解答斐波那契数列的动态规划代码,后续对此进行更改
        dp[1] = dp[2] = 1;
        for (int i = 3; ; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
  1. 因为输入的数据会出现不以1,1,2...开头的数据,而是2,2,4,6 ....等等,我们不能只计算以1开始的斐波那契数列,所以我们暴力遍历1-1000000开始的所有数列,并以修改次数最小的那次遍历作为答案,所以我们可以定义函数int dp(int start),返回以start开始的数列与原数组需要修改的次数
    public static int dp(int start) {
        // range代表dp数组的范围,因为dp数组大小只有100,遍历arr数组会超过dp数组的范围
        int range = 2;
        dp[1] = dp[2] = start;
        for (int i = 3; ; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
            // 数据范围在1000000以内
            if (dp[i] > 1000000) break;
            range++;
        }
        int ans = 0;
        for (int i = 1; i <= range; i++) {
            if (arr[i] == dp[i]) {
                ans++;
            }
        }
        return n - ans;
    }
  1. 暴力遍历,答案为每一个数字开始的数组中修改最少次数的那一次
        int ans = Integer.MAX_VALUE;
        for (int i = 1; i <= 1000000; i++) {
            int cur = dp(i);
            ans = Integer.min(cur, ans);
        }
        System.out.println(ans);
  1. 需要注意一点,就是我为什么会暴力遍历1-1000000 的dp数列,因为求斐波那契数列的过程非常快,然后剪枝掉超过数据范围的循环,因为以1开始的斐波那契数列在31项时就会超过1000000,那么每次遍历不会循环2(31)次,所以可以暴力解此题

完整代码

package lanqiao.java13cFinal;

import java.util.Scanner;

public class E {
    static int N = 100005;
    static int n;
    static int[] arr = new int[N];
    static int[] dp = new int[100];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            arr[i] = sc.nextInt();
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 1; i <= 1000000; i++) {
            int cur = dp(i);
            ans = Integer.min(cur, ans);
        }
        System.out.println(ans);
    }

    public static int dp(int start) {
        int range = 2;
        dp[1] = dp[2] = start;
        for (int i = 3; ; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
            if (dp[i] > 1000000) break;
            range++;
        }
        int ans = 0;
        for (int i = 1; i <= range; i++) {
            if (arr[i] == dp[i]) {
                ans++;
            }
        }
        return n - ans;
    }
}

热门相关:骑士归来   修仙界最后的单纯   法医王妃不好当!   朕是红颜祸水   豪门重生盛世闲女