动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。

思想：

在动态规划中，动态指的是问题可以被分解成一个个子问题，并且随着子问题的不断求解，可以得到原问题的最优解。因此，动态规划的关键在于定义状态和状态转移方程。

将原问题分解成若干个子问题，并记忆每个子问题的解，避免重复计算子问题。这样，在求解大问题时，就会通过不断地解决子问题来逐步缩小问题规模，直到解决大问题。

动态规划中的“动态”体现在两个方面：

1. 随着子问题的求解，原问题的解也在不断地发生变化，即原问题的最优解是基于其子问题的最优解而得出的。因此，动态规划中需要不断地更新状态和状态转移方程。
2. 由于问题具有“无后效性”，即问题的后续状态只与前面的状态有关，而不受未来事件的影响，因此动态规划中的状态可以被看做是一种“状态随时间推移而变化”的动态过程。

总之，动态规划指的是通过不断地解决子问题，逐步求解原问题并更新状态和状态转移方程的过程。

例子：leet code原题  70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

public class ClimbStairs{
    public static void main(String[] args) {
        final long start = System.nanoTime();
        System.out.println(climbStairs(300));
        System.out.printf("耗时(纳秒)：%d%n",System.nanoTime()-start);
    }


    public static int climbStairs(int n){
        if (n<=1){
            return 1;
        }
        if (n==2){
            return 2;
        }
        int a=1;
        int b=2;

        for (int i=3;i<=n;i++){
            b=a+b;
            a=b-a;
        }
        return b;
    }

}

解析：

1. 设跳上第n级台阶的跳法数量为f(n)
2. 由于要求只能爬1或2，那么到达楼顶必须要经过n-1和n-2,所以f(n)=f(n-1)+f(n-2)
3. 通过循环可以依次计算出f(n-1)+f(n-2)，最后的b就是通往第n个台阶的方法总数（斐波那契数列）