动态规划(一)

斐波那契数列

F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)

很容易就可以写出如下的代码：

    int fib(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        } else {
            return fib(n - 1) + fib(n - 2);
        }
    }

如果我们计算fib(5)的时候，他的递归树如下图所示：

仅仅计算第5个值的时候，函数就要递归如此多次，而且，有很多次都是重复计算的。
如果我们计算fib(100)的话，哪会有很多很多次重复的计算。

记忆化搜索

为了避免重复的计算，我们可以计算好的结果存到一个容器中，如果之前已经计算了我们需要的值，我们直接返回就可以了，不需要重复的计算。

    int fib(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("n value must be > 0");
        }
        int[] memo = new int[n + 1];
        // 初始化数组中的值都为-1
        // 初始化为-1的原因是因为fib计算的结果不可能是-1，都是大于等于0的
        for (int i = 0; i < memo.length; i++) {
            memo[i] = -1;
        }
        return fibCore(n, memo);
    }

    int fibCore(int n, int[] memo) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (memo[n] == -1) {
            // 之前没有计算过该值，需要计算
            memo[n] = fibCore(n - 1, memo) + fibCore(n - 2, memo);
        }
        return memo[n];
    }

上面这种解决问题的方式自上而下的解决，即我们先不算fib(n),而是算fib(n-1)和fib(n-2),一直这样 递推下去，知道出现f(0)或者f(1)才终止。

我们可以反过来，自上而下的解决这个问题，即先计算fib(0),fib(1),fib(2)...fib(n),代码如下：

    int fib(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("n value must be > 0");
        }
        int[] memo = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            if (i <= 1) {
                memo[i] = i;
            } else {
                memo[i] = memo[i - 1] + memo[i - 2];
            }
        }
        return memo[n];
    }

动态规划
将原问题拆解成若干个子问题，同时保存子问题的答案，使得每个子问题的求解只求一次，最终获取原问题的答案。

爬楼梯

题目
假设有一个楼梯，一次可以上一个，或者上两个，问，上n阶台阶，有多少种解法？

我们上第n阶台阶我们可能是在n-1阶台阶或者n-2阶台阶，而我们上n-1阶台阶可能是n-1-1或者n-1-2阶台阶。依次类推，直到我们上第2阶台阶或者第1阶台阶时结束，上第1阶台阶时，只有一种，而上第二阶台阶时可以是1+1或者2，所以有两种。这样我们的代码可以是这样的。

int climb(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            // 直接爬2阶或者一阶一阶爬
            return 2;
        }
        return climb(n - 1) + climb(n - 2);
    }

我们设想爬第0阶台阶，我们只有一种，就是没有嘛~，这样我们爬第二阶台阶也可以通过climb(1)+climb(0)计算出来，于是，我们的代码就变成了这样：

    int climb(int n) {
        if (n <= 1) {
            return 1;
        }
        return climb(n - 1) + climb(n - 2);
    }

细心的小伙伴可以看出，这个就是我们刚刚写的斐波那契数列。

Triangle

给定一个三角形的数字阵列，选择一条自顶向下的路径，使得沿途的所有数字之和最小（每一步只能移动到相邻的格子中）
eg:

最小路径为：2+3+5+1=11

MiniMum Path Sum

给出一个m*n矩阵，其中每一个格子包含一个非负的整数，寻找一条从左上角到右下角的路径，使得沿路的路径之和最小。
【注意】每次只能向下或者向右移动。