2019-02-01

喵星之旅-阴险的布谷鸟-动态规划

简介

动态规划（Dynamic Programming，简称DP）是一种解决多阶段决策问题的数学优化方法。它将原问题分解成若干个子问题，通过解决子问题只需解决一次并将结果保存下来，从而避免了重复计算，提高了算法效率。动态规划算法是解决一类具有重叠子问题和最优子结构性质的问题的有效方法。

动态规划算法的基本原理是将大问题分解为小问题，通过保存中间结果来避免重复计算，从而提高算法的效率。它主要包括两个要素：最优子结构和重叠子问题。最优子结构指的是问题的最优解可以由其子问题的最优解递归地构建而成。而重叠子问题则是指在解决子问题时，有些子问题会被重复计算多次。

动态规划算法在很多领域都有广泛的应用，如背包问题、最长递增子序列、最大子数组和问题等。然而，当需要处理的数据规模较大时，使用动态规划算法也存在超时的可能性。因此，在实际应用中，我们需要在动态规划的基础上做出优化，如使用空间换时间、无后效性、剪枝、与贪心算法结合等方法，以提高算法的性能。

总的来说，动态规划算法是一种非常强大且有效的优化方法，适用于解决具有重叠子问题和最优子结构性质的多阶段决策问题。

主要实现步骤

动态规划算法的基本步骤包括：

定义状态：确定问题的状态，将大问题分解为子问题，并确定子问题所对应的状态。
确定状态转移方程：找到子问题之间的关系，并建立状态转移方程。
初始化边界条件：确定基本情况的解，为后续的状态转移提供依据。
根据状态转移方程，从小规模问题开始逐步推导，直到求解出原问题的最优解。

也可以认为可用数列的方式认知的问题都可以采用该法。转移方程也就是递推公式。采用初始值和递推式逐一计算数列值的过程就是动态规划。

例题

题目

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

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

其中：1 <= n <= 45

示例

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。

1 阶 + 1 阶
2 阶

示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。

1 阶 + 1 阶 + 1 阶
1 阶 + 2 阶
2 阶 + 1 阶

解答

public int climbStairs(int n) {
    int p = 0, q = 0, r = 1;
    for (int i = 1; i <= n; ++i) {
        p = q; 
        q = r; 
        r = p + q;
    }
    return r;
}