• 动态规划三大重要概念：最优子结构，边界，状态转移公式（问题规模降低，如问题由 n 的规模降低为 n−1 或 n−2 及二者之间的关系）；

0. 爬台阶

• F(n−1),F(n−2) 即是 F(n) 的最优子问题；
• F(1)=1,F(2)=2 是问题的边界；
• F(n)=F(n−1)+F(n−2) 则是问题的状态转移公式；

1. 数列快速求和和矩阵快速乘法

也即：f(n)=2⋅f(n2)+n24 ⇒ 问题的规模以 n/2 的缩小，时间复杂度从 O(n) 变为 O(logn)；

int fastSum(int n){

    if (n == 1) return 1;

    if (n % 2) return fastSum(n-1) + n;

    return 2*fastSum(n/2)+n/2*n/2;

}