题目描述
如果数组 A = (a0, a1, · · · , an−1) 满足以下条件，就说它是一个斐波那契数组：
-
n ≥ 2；
-
a0 = a1；
-
对于所有的 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
解答
- 这道题是典型的斐波那契数列题，而且因为题目的数据范围很大，使用暴力递归几乎全部数据都会超时，所以我们使用动态规划进行解答
- 写出基本的解答斐波那契数列的动态规划代码，后续对此进行更改
dp[1] = dp[2] = 1;
for (int i = 3; ; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
- 因为输入的数据会出现不以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;
}
- 暴力遍历，答案为每一个数字开始的数组中修改最少次数的那一次
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-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;
}
}