动态规划(dynamic programming)是数据结构与算法中常用到的策略算法，一般是通过状态转移方程和初始状态来一起定义问题，从而将更大的问题转换为前面已经计算出结果的动态的更新的过程。动态规划的难点在于状态转移方程的定义，有得问题比较显而易见，而有的问题可能就比较难以定义，需要多从实际问题中总结相关的经验。
今天向大家介绍动态规划的三个示例，具体一一向大家进行介绍。
实例1：爬楼梯问题，也是经典的动态规划问题，描述如下：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
分析及解答，假设爬到n阶有methods[n]种方法，则有两种可能，先爬到n-2阶，然后跨2个台阶到达n阶，或者先爬到n-1阶，然后跨1个台阶达到n阶。因此状态转移方程为：dp[n]=dp[n-1]+dp[n-2]。初始状态为dp[0]=0,dp[1]=1,dp[2]=2。然后就可以用递推来进行循环计算了。
实例2：找零钱问题，给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是无限的。
分析及解答：假设所需最少的硬币个数为f[amount]，则状态转移方程可以表示为f[amount]=min(f[amount-conins[j]+1)，其中要求满足amount-conins[j]>0的所有的j。在递推求解的过程中，可以用双重循环来实现，外层从1到amount，内层j从0到硬币的个数-1，然后循环有个条件，及当前amount-coins[j]要大于零。
实例3：给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。假设每一种面额的硬币有无限个。
分析和解答：这是和第二个问题相似但思路差别较大的问题，这里不做详细分析，直接先给出状态转移方程并作出一定的解释。状态转移方程为：problem(k,i) = problem(k-1, i) + problem(k, i-k)。其中problem(k,i) 为一个二维的状态，其中第一个维度表示用到了前面的k个硬币，i表示当前的凑的金额。problem(k-1, i)表示只用到了前面k-1个硬币就已经凑到了i，不需要第k个硬币，problem(k, i-k)表示用到了前面k个硬币凑到了i-k，已经用到了第k个硬币。
关于代码实现，后续有机会再向大家进行分享，也希望自己后面有机会向大家逐步整理关于数据结构和算法的较为系统全面的介绍，欢迎大家提出意见和建议。
Leave a Reply