动态规划和递归法求解斐波那契数列

动态规划是把复杂问题分解为相对简单的子问题来求解,动态规划旨在解决具有重叠子问题和最优子结构特性的问题,它的核心思想是解决每个子问题仅能一次,并存储其解,以便需要时直接查找,从而避免重复计算
基本概念:
1.重叠子问题:
问题可以分解为多个子问题,且这些子问题有些会被多次计算.动态规划通过存储子问题的解来避免重复计算
2.最优子结构:
原问题的最优解可以通过其子问题的最优解组合得出.这意味着问题的最优解包含了其子问题的最优解

示例:

package a_od_test;
/*
斐波那契数列
0 1 1 2 3 5 ...

示例1:
输入:
1
输出:
1

示例2:
输入:
4
输出:
3

解题思路:
递归法
动态规划法

 */
public class Main34_Test {
    public static void main(String[] args) {
        //递归法
//        int result = recursion(4);
        //动态规划法
        int result = dynamicProgramming(4);
        System.out.println(result);
    }


    public static int recursion(int n) {
        if (n <= 1) {
            return n;
        } else {
            return recursion(n - 1) + recursion(n - 2);
        }
    }

    public static int dynamicProgramming(int n) {
        if (n <= 1) {
            return n;
        }
        //先创建一个数组来保存历史数据
        int[] dp = new int[n + 1];
        //给出初始值
        dp[0] = 0;
        dp[1] = 1;
        //通过关系式来计算出dp[n]
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        //把最终结果返回
        return dp[n];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58