动态规划算法

题目： 有一座高度是10级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法。
比如，每次走1级台阶，一共走10步，这是其中一种走法。我们可以简写成 1,1,1,1,1,1,1,1,1,1。

动态规划的英文名Dynamic Programming, 是一种分阶段求解决策问题的数学思想。它不止用于编程领域，也应用于管理学、经济学、生物学。

把一个复杂的问题分阶段进行简化，逐步简化成简单问题。这就是动态规划的思想。

  那刚才的面试题目来说，假设你只差最后一步就走到第10级台阶，这时候会出现几种情况？当然是两种情况了，第一种是从9级走到10级，第二种是从8级走到10级。
   因此， 10级台阶的走法可以根据最后一步的不同分成两部分，第一部分的最后一步是从9级到10级，这部分的走法数量和9级的走法数来数量是相等的。因为这部分的最后一步是固定的，走与不走最后一步走法是确定的。同理，第二部分的最后一步是从8级走到10级，这部分的走法数量和8级的走法数量是相等的。

如果我们已知0到9级台阶的走法有X中，0到8级台阶有Y中走法，那么0到10级台阶就有X+Y中走法。
F（10） = F（9） + F（8）

结论：
F(1) = 1;
F(2) = 2;
F(n) = F(n-1)+F(n-2)（n>=3）

动态规划中有三个重要概念：
最优子结构 F（10） = F（9） + F（8）
边界 F(1) = 1; F(2) = 2;
状态转移方程 F(n) = F(n-1)+F(n-2)（n>=3）

代码实现：

package com.zheting.it.test04;

public class Test {

    public static void main(String[] args) {
        int climbingWays = getClimbingWays(10);
        System.out.println(climbingWays); //89
    }

    public static int getClimbingWays(int n) {
        if (n < 1) {
            return 0;
        }

        if (n == 1) {
            return 1;
        }

        if (n == 2) {
            return 2;
        }

        int a = 1;
        int b = 2;
        int temp = 0;
        for (int i = 3; i <= n; i++) {
            temp = a + b;
            a = b;
            b = temp;
        }
        return temp;
    }
}

题目（未完）：
有一个国家发现了5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人数也不同。参与挖矿工人的总数是10人。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半金矿。要求用程序求解出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？

金矿数量设为N, 工人数量设为W, 金矿的黄金量设置为数据G[], 金矿的用工量设为数组P[]
F(n,w) = 0 (n<=1, w<p[0]);

F(n,w) = g[0] (n==1, w>=p[0]);

F(n,w) = F(n-1,w) (n>1, w<p[n-1])

F(n,w) = max(F(n-1,w), F(n-1,w-p[n-1])+g[n-1]) (n>1, w>=p[n-1])

原文：http://www.sohu.com/a/153858619_466939