本章内容动态规划

动态规划又称记忆化搜索、递归树的剪枝。

动态规划的特点：

重叠子问题。状态转移方程。最优子结构。

动态规划的应用场景：

求最值，如：求最大值/最小值、最长递增子序列、最小编辑距离等。

动态规划的解题思路：

1.暴力穷举：通过状态转移方程，暴力穷举所有可行解。2.优化穷举：1）使用备忘录消除重叠子问题（即：带备忘录的递归算法）。2）通过暴力穷举解法推导出自底向上的迭代解法（即：动态规划算法）。3）最后优化空间复杂度（可选）。

动态规划的解题套路：

1）明确状态。2）找出最优子结构。3）写出状态转移方程。4）明确边界。零钱兑换问题

给定不同面额的硬币coins和一个总金额amount，编写一个函数来计算可以凑成总金额所需要的最少硬币个数，如果没有任何一种硬币组合能组成总金额，则返回-1。注：每种硬币的数量无限制。

假如：给定不同面额的硬币：coins=[1,2,5]，目标总金额为：11，求解凑成目标总金额所需要的最少硬币个数。

示例：

输入：coins = [1, 2, 5], amount = 11输出：3解释：11 = 5 + 5 + 1输入：coins = [2], amount = 3输出：-1输入：coins = [1], amount = 0输出：0

解题思路

将所有可能的解法穷举成树状结构。如图所示：

图中，自顶向下：

求解目标金额f(11)所需要的最少硬币数有三种选择，分别是：f(11)-1=f(10)、f(11)-2=f(9)、f(11)-5=f(6)。求解目标金额f(10)所需要的最少硬币数有三种选择，分别是：f(10)-1=f(9)、f(10)-2=f(8)、f(10)-5=f(5)。求解目标金额f(9)所需要的最少硬币数有三种选择，分别是：f(9)-1=f(8)、f(9)-2=f(7)、f(9)-5=f(4)。求解目标金额f(6)所需要的最少硬币数有三种选择，分别是：f(6)-1=f(5)、f(6)-2=f(4)、f(6)-5=f(1)。......求解目标金额f(1)所需要的最少硬币数有三种选择，分别是：f(1)-1=f(0)、f(1)-2=f(-1)、f(1)-5=f(-1)。

以此类推，自顶向下依次求解，直到节点f(0)或f(-1)。即：如果要求解某个目标金额所需要的最少硬币数，只需要将目标金额减去一枚不同面额的硬币即可得到该目标金额子节点所需要的最少硬币数（这点很重要），依此方式自顶向下递归，就可以得出目标金额所需要的最少硬币数。

注意：

f(-1)表示不能求得目标金额。连线上的值表示不同面额的硬币。

代码实现

/** * @author 南秋同学 * 零钱兑换-暴力穷举解法 */public class CoinChange {    /**     * 求解目标总金额所需要的最少硬币数     * @param coins 不同面额的硬币     * @param amount 目标总金额     * @return 返回目标总金额所需要的最少硬币数     */    public static int coinChange(int[] coins, int amount){        // 明确边界        if(amount == 0){            return 0;        }        if(amount < 0){            return -1;        }        int response = Integer.MAX_VALUE;        for(int coin: coins){            // 计算子问题，如：coin为面额为5的硬币，则继续求amount-5的目标总金额所需要的最少硬币数            int subProblem = coinChange(coins, amount-coin);            // 如果子问题计算结果为-1（即：amount<0），则直接跳过。            if(subProblem == -1){                continue;            }            /*                在子问题中选择最优解，然后+1（注意：+1的原因是子问题已经是最少硬币数，再+1枚硬币得到的所需硬币数自然就是目标总金额所需的最少硬币数。                如：子问题min(coinChang([1,2,5],10))、min(coinChang([1,2,5],9))、min(coinChang([1,2,5],6))求得的最少硬币数                再+1枚面额为1、2、5的硬币就是目标总金额的最少硬币数）。             */            response = Math.min(response, subProblem+1);        }        System.out.println("求解目标金额：" + amount + "，所需要的最少硬币数为：" + response);        // 返回目标总金额所需要的最少硬币数        return response == Integer.MAX_VALUE ? -1 : response;    }    public static void main(String[] args) {        System.out.println("求解目标总金额所需要的最少硬币数为："+CoinChange.coinChange(new int[]{1,2,5}, 11));    }}

复杂度

暴力穷举解法是将一个问题分解成多个子问题，本题的计算公式为：求解目标金额所需要的最少硬币数f(n)-不同面额的硬币=子问题所需要的最少硬币数，时间复杂度为O(1)；子问题个数为递归树节点个数-1，时间复杂度为O(3^n)。因此，暴力穷举解法的时间复杂度为：O(1)*O(3^n)=O(3^n)。

带备忘录的递归解法

解题思路

将所有可能的解法穷举成树状结构，并通过相同颜色标明重复的节点。如图所示：

图中：

同颜色节点（白色除外）表示存在重复计算的节点。节点-1表示不能求得目标金额。

待备忘录的递归解法是在暴力穷举解法的基础上使用一个备忘录存储各个子问题的计算结果（即：去除相同颜色节点的重复计算）。

去除树状结构中相同颜色节点（即：相同颜色只保留一个结果）后的结构如图所示：

代码实现

/** * @author 南秋同学 * 零钱兑换-带备忘录的递归解法 */public class CoinChange {    /**     * 定义备忘录     */    int[] memo;    /**     * 求解目标总金额所需要的最少硬币数     * @param coins 不同面额的硬币     * @param amount 目标总金额     * @return 返回目标总金额所需要的最少硬币数     */    public int coinChange(int[] coins, int amount){        // 初始化备忘录        memo = new int[amount+1];        // 将备忘录中的元素初始化为特殊值-222（该值为任意负数，即：非有意义的值即可）        Arrays.fill(memo, -222);        // 递归求解目标总金额所需要的最少硬币数        return dp(coins, amount);    }    private int dp(int[] coins, int amount){        // 明确边界        if(amount == 0){            return 0;        }        if(amount < 0){            return -1;        }        // 如果amount在备忘录中已经存在非-222的值，说明已经计算过该值，则直接返回该值        if(memo[amount] != -222){            return memo[amount];        }        int response = Integer.MAX_VALUE;        for(int coin:coins){            // 计算子问题，如：coin为面额为5的硬币，则继续求amount-5的目标总金额所需要的最少硬币数            int subProblem = dp(coins, amount - coin);            // 如果子问题计算结果为-1（即：amount<0），则直接跳过。            if (subProblem == -1) {                continue;            }            /**             * 在子问题中选择最优解，然后+1（注意：+1的原因是子问题已经是最少硬币数，再+1枚硬币得到的所需硬币数自然就是目标总金额所需的最少硬币数。             * 如：子问题min(coinChang([1,2,5],10))、min(coinChang([1,2,5],9))、min(coinChang([1,2,5],6))求得的最少硬币数             * 再+1枚面额为1、2、5的硬币就是目标总金额的最少硬币数）。             */            response = Math.min(response, subProblem + 1);        }        System.out.println("求解目标金额：" + amount + "，所需要的最少硬币数为：" + response);        // 将计算结果加入备忘录中        memo[amount] =(response == Integer.MAX_VALUE ? -1 : response);        // 返回目标总金额所需要的最少硬币数        return memo[amount];    }    public static void main(String[] args) {        System.out.println("求解目标总金额所需要的最少硬币数为："+ new CoinChange().coinChange(new int[]{1,2,5}, 11));    }}

复杂度

待备忘录的递归算法是在暴力穷举算法基础上增加了备忘录优化，求解目标金额所需要的最少硬币数f(n)-不同面额的硬币=子问题所需要的最少硬币数，时间复杂度为O(1)；子问题个数为递归树节点个数-1，时间复杂度为O(n)。因此，待备忘录的递归算法的时间复杂度为：O(1)*O(n)=O(n)。

动态规划解法

与带备忘录的自顶向下的递归解法类似，动态规划算法是一种自底向上的迭代解法，通过拆分子问题，计算并存储子问题计算结果，自底向上迭代求得目标值。

解题思路

1）明确状态，本题中提供的参数有两个：不同面额的硬币coins和目标金额amount，其中目标金额amount确定，硬币coins有三种选择，因此，状态为coins。

2）找出最优子结构，本题的问题是根据不同面额的硬币求解目标金额所需要的最少硬币数，可以先将该问题拆分为三个结构相同的子问题，分别求解子问题所需要的最少硬币数，最后加上一枚不同面额的硬币就得到目标金额所需要的最少硬币数。即：

求解金额为10所需要的最少硬币数+1枚面额为1的硬币=目标金额11所需要的最少硬币数。求解金额为9所需要的最少硬币数+1枚面额为2的硬币=目标金额11所需要的最少硬币数。求解金额为6所需要的最少硬币数+1枚面额为5的硬币=目标金额11所需要的最少硬币数。

其中金额为10、9、6所需要最少硬币数中的最小值即为最优子结构。

3）写出状态转移方程，状态转移方程其实就是db函数，即：根据不同面额的硬币递归求解目标金额的过程。

4）明确边界，本题中边界为amount+1（即：目标金额所需要的最少硬币数不可能大于目标金额值）。

如图所示：

代码实现

/** * @author 南秋同学 * 零钱兑换-动态规划解法 */public class CoinChange {    /**     * 求解目标总金额所需要的最少硬币数     * @param coins 不同面额的硬币     * @param amount 目标总金额     * @return 返回目标总金额所需要的最少硬币数     */    public static int coinChange(int[] coins, int amount){        // 定义dp数组，表示要得到目标金额amount，所需要的最少硬币数为dp[amount]（即：下标为目标金额，下标对应的值为最少硬币数）        int[] dp = new int[amount+1];        // 数组元素初始化大小需要大于amount值。        Arrays.fill(dp, amount+1);        // 从0开始        dp[0] = 0;        // 遍历dp数组        for(int i = 0; i< dp.length; i++){            for(int coin:coins){                // 如果目标金额小于coin面额，则跳过                if(i -coin < 0){                    continue;                }                // 状态转移，即：要获取dp[i]所需最少硬币数，则需要先获取dp[i-coin]所需最少硬币数，再将dp[i-coin]+1与dp[i]比较，取最少硬币数。                dp[i] = Math.min(dp[i], dp[i-coin]+1);            }            System.out.println("求解目标金额：" + i + "，所需要的最少硬币数为：" + dp[i]);        }        // 可以得到目标金额，则返回目标金额，否则返回-1，注意：此处amount+1为db数组元素的初始化值（即：边界）        return (dp[amount] == amount+1) ? -1 : dp[amount];    }    public static void main(String[] args) {        System.out.println("求解目标总金额所需要的最少硬币数为："+ CoinChange.coinChange(new int[]{1,2,5}, 11));    }}

复杂度

动态规划算法与待备忘录的递归算法类似，求解目标金额所需要的最少硬币数f(n)=子问题+不同面额的硬币，时间复杂度为O(1)；子问题个数为递归树节点个数-1，时间复杂度为O(n)。因此，动态规划算法的时间复杂度为：O(1)*O(n)=O(n)。

【阅读推荐】

想了解其他常用算法（如：堆与堆排序、快速排序、二分查找等）的童鞋请移步->算法系列合集（持续更新中）。

更多内容持续更新中......

【作者简介】

一枚热爱技术和生活的老贝比，专注于Java领域，关注【南秋同学】带你一起学习成长～