题解 | #斐波那契数列#

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型
     */
    int Fibonacci(int n) {
        // write code here
        if (n == 1 || n == 2) return 1;
        else
            return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
};

动态规划（Dynamic Programming，简称 DP）是一种用于解决多阶段决策问题的数学方法。它通常用于优化问题，通过将问题分解为一系列子问题，然后解决这些子问题，最终组合它们的解来解决原始问题。

动态规划的一般步骤包括：

1. 定义子问题： 将原始问题分解为一系列子问题，每个子问题对应一个决策点。
2. 定义状态： 定义表示问题的状态，并确定状态之间的关系。状态是问题的某个特定阶段的描述。
3. 确定递推关系： 找到问题状态之间的递推关系式，即用较小规模的子问题的解来表示较大规模问题的解。
4. 初始化边界条件： 设置问题的边界条件，通常是最小规模问题的解。
5. 计算顺序： 选择合适的计算顺序，通常是自底向上（bottom-up）或自顶向下（top-down）。
6. 计算最终解： 根据递推关系和边界条件计算原始问题的解。

求Fibonacci(int n) 转换成求Fibonacci(n - 1) + Fibonacci(n - 2) ，Fibonacci(n - 2) + Fibonacci(n - 3) +Fibonacci(n - 3) + Fibonacci(n - 4)。 一层层下去，最后都是 a*Fibonacci(1) + b*Fibonacci( 2) 那么我们需要给出1，2时的对应处理。剩下的就是一层层套。