題目要求

P1028題目要求

分析

我們可以用遞歸做，但可能會超時或者超內(nèi)存。最起碼不算好的算法。

那么我們就可以考慮找到遞推規(guī)律，利用簡單的DP處理。

在迭代的時候發(fā)現(xiàn)：(i >= 2)
i為偶數(shù)的時候，存在：f(i) = f(i-1) + f(i/2)
i為奇數(shù)的時候，存在：f(i) = f(i-1)

做一下簡單模擬：
n = 0, result = 1;
n = 1, result = 1;
n = 2, result = 2;
n = 3, result = 2;
n = 4, result = 4;
n = 5, result = 4
n = 6, result = 6;
n = 7, result = 6;

符合我們所寫的方程。

AC代碼（Java語言描述）

import java.util.Scanner;public class Main {public static void main(String[] args) {int[] f = new int[1001];f[0] = f[1] = 1;Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();scanner.close();for(int i = 2; i <= n; i++){if(i % 2 == 0){f[i] = f[i-1] + f[i/2];} else {f[i] = f[i-1];}}System.out.println(f[n]);} }

總結(jié)

以上是生活随笔為你收集整理的递归不行就换动态规划（洛谷P1028题题解，Java语言描述）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。