找零钱问题的最优子结构性质及动态规划算法分析与设计

本实验的题目是找零钱问题，要求设计一个算法，用最少的钞票张数找给顾客。每种钞票都有足够的张数。首先需要进行符号的说明，n表示零钱的种数。 本实验采用了两种动态规划算法来解决这个问题。首先是自底向上的动态规划算法，然后是备忘录法。下面将对这两种算法进行详细的描述。 自底向上的动态规划算法的主要思想是，从较小的子问题开始解决，逐步推导出较大的子问题的解，最终得到整个问题的解。具体步骤如下： 1. 创建一个长度为amount+1的一维数组dp，dp[i]表示得到金额为i所需的最少钞票张数。 2. 初始化dp数组，将所有元素初始化为正无穷大，除了dp[0]设置为0。 3. 遍历钞票面额的种类，对于每一种面额，从金额1开始，计算得到的最少钞票张数。假设当前面额为coin，遍历金额为i的情况，更新dp[i] = min(dp[i], dp[i-coin]+1)。 4. 输出dp[amount]，即找零所需的最少钞票张数。 备忘录法是动态规划的一种优化方法，其主要思想是通过记录已经计算过的子问题的解来避免重复计算。具体步骤如下： 1. 创建一个长度为amount+1的一维数组memo，memo[i]表示金额为i时的最少钞票张数。初始情况下所有元素设置为-1。 2. 创建递归函数helper，接收一个参数amount，返回金额为amount时的最少钞票张数。 3. 在helper函数中，首先判断是否已经计算过memo[amount]的值，如果计算过则直接返回memo[amount]。否则，将memo[amount]设置为正无穷大，然后遍历钞票面额的种类，计算得到金额为amount所需的最少钞票张数，并更新memo[amount]的值。 4. 返回memo[amount]，即找零所需的最少钞票张数。 实验要求至少运行3组不同的输入数据，并用两种方法求解，即动态规划和备忘录法。 本实验使用Java编程语言完成算法设计和程序设计，并成功调试通过。 总结以上所述，本实验通过自底向上的动态规划算法和备忘录法解决了找零钱问题，并满足了实验要求。