动态规划是一种用来优化递归问题的方法，通过将重叠子问题的解存储起来以避免重复计算，从而提高效率。在Java中实现动态规划来求解斐波那契数列是一个经典的例子。

斐波那契数列简介

斐波那契数列的定义如下：
- F(0) = 0
- F(1) = 1
- F(n) = F(n-1) + F(n-2) 对于 n >= 2

动态规划实现

我们将通过实现一个简单的动态规划解决方案来计算斐波那契数列的第 n 项。这种方法通常称为“带备忘录的自顶向下法”或者“自底向上法”。自底向上方法即是常用的动态规划方法。

自底向上（迭代法）

这种方法使用数组来存储已经计算过的斐波那契数，从而避免重复计算。

public class Fibonacci {  
    public static long fibonacci(int n) {  
        if (n <= 1) {  
            return n;  
        }  
        long[] fib = new long[n + 1];  
        fib[0] = 0;  
        fib[1] = 1;  
        for (int i = 2; i <= n; i++) {  
            fib[i] = fib[i - 1] + fib[i - 2];  
        }  
        return fib[n];  
    }  
    public static void main(String[] args) {  
        int n = 10; // Example value  
        System.out.println("Fibonacci of " + n + " is " + fibonacci(n));  
    }  
}  

空间优化的迭代法

我们实际上只需要维护前两个数字即可，而不是整个数组，从而优化空间复杂度。

public class Fibonacci {  
    public static long fibonacci(int n) {  
        if (n <= 1) {  
            return n;  
        }  
        long prev1 = 0;  
        long prev2 = 1;  
        long result = 0;  
        for (int i = 2; i <= n; i++) {  
            result = prev1 + prev2;  
            prev1 = prev2;  
            prev2 = result;  
        }  
        return result;  
    }  
    public static void main(String[] args) {  
        int n = 10; // Example value  
        System.out.println("Fibonacci of " + n + " is " + fibonacci(n));  
    }  
}  

复杂度分析

• 时间复杂度: O(n)，因为我们只需循环一次即可计算出结果。
• 空间复杂度: O(1)，对于优化的迭代法，只需要常量级别的空间来存储几个变量。

这种方法显著提升了效率，相比于递归方法，也避免了深度递归带来的栈溢出风险。