动态规划假定pos机中（动态规划可利用什么一步步得到问题的最优解）



1、动态规划假定pos机中

动态规划：POS 机中的假设

1. 状态定义

动态规划将复杂问题分解成一系列更小的子问题，并对子问题的最优解进行组合以求得原问题的最优解。在 POS 机中，状态可以定义为：

阶段 (i)：当前处理的邮票面值

剩余金额 (j)：需要找零的金额

2. 状态转移方程

对于每个状态 (i, j)，我们可以考虑使用面值为 i 的邮票找零 j 的方案。有两种可能：

选择：使用邮票面值 i，剩余金额变为 j - i；

不选择：不使用邮票面值 i，剩余金额保持为 j。

因此，状态转移方程为：

dp[i][j] = min(dp[i][j - i] + 1, dp[i + 1][j])

其中：

dp[i][j] 表示找零金额为 j 时使用面值为 i 的邮票的最少张数；

dp[i][j - i] 表示找零金额为 j - i 时使用面值为 i 的邮票的最少张数；

dp[i + 1][j] 表示不使用面值为 i 的邮票找零金额为 j 时最少张数。

3. 边界条件

当 j = 0 时，找零金额为 0，需要 0 张邮票。因此，边界条件为：

```

dp[i][0] = 0

```

4. 最优解

对于给定的找零金额 n，最优解存储在 dp[0][n] 中，它表示找零金额为 n 时使用最少张邮票的方案。

5. 复杂度分析

状态数为 O(n m)，其中 n 为邮票面值的数量，m 为找零金额的最大值。状态转移方程需要 O(1) 的时间，因此总时间复杂度为 O(n m)。

2、动态规划可利用什么一步步得到问题的最优解

动态规划：逐层求解问题的最优解

什么是动态规划？

动态规划是一种解决复杂问题的算法，通过将问题分解成更小的子问题，逐步求解，从而得到问题的最优解。动态规划以其将重叠子问题存储并在需要时重复利用的能力而闻名。

动态规划的步骤：

1. 确定子问题：

将原问题分解成更小的、相互重叠的子问题。

2. 定义子问题的最优解：

为每个子问题定义其最优解的递归关系。

3. 创建存储数组：

创建一个数组来存储已解子问题的最优解。

4. 逐层求解子问题：

从最简单的子问题开始，逐步求解更复杂的子问题，将已解决的子问题的最优解存储在存储数组中。

5. 得出原问题的最优解：

通过合并子问题的最优解，得出原问题的最优解。

动态规划的优势：

记忆化：存储已解决子问题的最优解，避免重复计算。

分而治之：将复杂问题分解成更小的、易于管理的子问题。

渐进式求解：逐层求解子问题，建立起最终解的基础。

动态规划的应用：

动态规划广泛应用于计算机科学和运筹学领域，包括：

最长公共子序列

背包问题

最短路径问题

编辑距离问题

3、请简述使用动态规划算法解题的基本步骤

使用动态规划算法解题的基本步骤

动态规划算法是一种用于求解最优化问题的算法，其通过分解问题为一系列子问题，并存储子问题的解来避免重复计算。其基本步骤如下：

1. 定义子问题：

将原问题分解为更小的、独立的子问题。每个子问题应具有明确的定义和可求解的输入和输出。

2. 定义递归关系：

描述子问题之间的关系。此关系应说明如何将子问题的解组合起来得到原问题的解。

3. 确定自底向上或自顶向下的计算顺序：

选择从子问题向原问题（自底向上）还是从原问题向子问题（自顶向下）的计算顺序。

4. 创建存储结构：

创建一种数据结构来存储子问题的解。此结构应允许快速访问和更新。

5. 初始化存储结构：

将边界子问题的解初始化为已知值。这通常是基础情况。

6. 迭代计算：

使用递归关系和存储结构，迭代计算子问题的解。从边界条件开始，逐步解决更大规模的子问题。

7. 获取最终解：

一旦计算完所有子问题的解，即可从存储结构中获取原问题的最终解。

示例：

设有长度为 n 的数组 arr，目标是找到数组中相邻元素的最大和。使用动态规划算法的步骤如下：

1. 定义子问题： 找到以 arr[i] 为结尾的相邻元素的最大和。

2. 定义递归关系： dp[i] = max(dp[i-1] + arr[i], arr[i])

3. 计算顺序： 自底向上

4. 创建存储结构： 一维数组 dp

5. 初始化存储结构： dp[0] = arr[0]

6. 迭代计算：

for i = 1 to n-1

dp[i] = max(dp[i-1] + arr[i], arr[i])

7. 获取最终解： dp[n-1]