python 实现动态规划
动态规划（Dynamic programming）
是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推的方式去解决，当前子问题的解将由上一个子问题的解推出。使用动态规划来解题只需要多项式时间复杂度，因此它比回溯法、暴力法等要快许多。
动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果。
动态规划中的子问题往往不是相互独立的（即子问题重叠）。在求解的过程中，许多子问题的解被反复地使用。为了避免重复计算，动态规划算法采用了填表来保存子问题解的方法,即带备忘录的递归，当需要某个子问题的解时，直接取值即可，从而避免重复计算。
适用问题
符合“一个模型三个特征”的问题。
“一个模型”：指 多阶段决策最优解模型；
“三个特征”：分别是最优子结构、无后效性和重复子问题。
（1）最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
（2）无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
（3）有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势。
这类问题的求解步骤通常如下：
初始状态→│决策1│→│决策2│→…→│决策n│→结束状态
（1）划分：按照问题的特征，把问题分为若干阶段。注意：划分后的阶段一定是有序的或者可排序的
（2）确定状态和状态变量：将问题发展到各个阶段时所处的各种不同的客观情况表现出来。状态的选择要满足无后续性
（3）确定决策并写出状态转移方程：状态转移就是根据上一阶段的决策和状态来导出本阶段的状态。根据相邻两个阶段状态之间的联系来确定决策方法和状态转移方程
（4）边界条件：状态转移方程是一个递推式，因此需要找到递推终止的条件
动态规划三要素：
（1）问题的阶段
（2）每个阶段的状态
（3）相邻两个阶段之间的递推关系
整个求解过程可以用一张最优决策表来描述，最优决策表是一张二维表（行：决策阶段，列：问题的状态）表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值（如最短路径，最长公共子序列，最大价值等），填表的过程就是根据递推关系，最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。
经典问题1：斐波那契数列
def fibonacci(n):
if n < 2:
return n
else:
return fibonacci(n - 1) + fibonacci(n - 1)
def dyna_fibonacci(n):
if n < 2:
return n
else:
a, b = 0, 1
for _ in range(n - 1):
a, b = b, a + b
return b
if __name__ == '__main__':
t1 = time.time()
fibonacci(100)
t2 = time.time()
dyna_fibonacci(100)
t3 = time.time()
print("Time required for using recursion:", t2 - t1)
print("Dynamic Planning Duration:", t3 - t2)
经典问题2：求两个字符串最大子串
def longest_subst(str1, str2):
maxlen, index = 0, 0
arr = [[0 for _ in range(len(str2) + 1)] for _ in range(len(str1) + 1)]
for i in range(1, len(str1) + 1):
for j in range(1, len(str2) + 1):
if str1[i - 1] == str2[j - 1]:
arr[i][j] = arr[i - 1][j - 1] + 1
else:
arr[i][j] = 0
if arr[i][j] > maxlen:
maxlen = arr[i][j]
index = j
return str2[index - maxlen:index]
print(longest_subst("1AB2345CD", "12345EF"))
使用了一个二维数组来存储子问题的最优解,通过两层循环遍历两个字符串的所有字符，当当前字符相等时，我们可以构成更长的公共子串，因此将 arr[i][j] 设置为左上角元素 arr[i - 1][j - 1] 的值加1。同时，我们不断更新最长公共子串的长度和结束位置。
最终，根据最长公共子串的长度和结束位置，我们可以找出最长公共子串。
经典问题3：背包问题
背包问题（Knapsack Problem）是一个经典的组合优化问题，在计算机科学和运筹学中被广泛研究和应用。该问题描述如下：给定一个背包容量和一组物品，每个物品都有一个重量和一个价值，我们的目标是选择一些物品放入背包中，使得放入背包的物品总重量不超过背包容量，并且物品的总价值最大化。
背包问题可以分为两种类型：0-1背包问题和无限背包问题。
0-1背包问题（0/1 Knapsack Problem）：每个物品最多只能选择一次放入背包中。即物品的选择是二进制的，要么放入背包，要么不放入。
无限背包问题（Unbounded Knapsack Problem）：每个物品可以选择多次放入背包中，即物品的选择是非负整数的。
下面是一个使用Python实现0-1背包问题的示例代码：
def knapsack_01(values, weights, capacity):
n = len(values)
# 创建一个二维数组来存储子问题的最优解
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, capacity + 1):
# 如果当前物品的重量超过背包容量，则无法放入背包
if weights[i - 1] > j:
dp[i][j] = dp[i - 1][j]
else:
# 考虑将当前物品放入背包和不放入背包两种情况，选择价值最大的
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])
# 获取最优解的价值
max_value = dp[n][capacity]
# 回溯找出选择的物品
selected_items = []
j = capacity
for i in range(n, 0, -1):
if dp[i][j] != dp[i - 1][j]:
selected_items.append(i - 1)
j -= weights[i - 1]
return max_value, selected_items
# 测试示例
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
max_value, selected_items = knapsack_01(values, weights, capacity)
print("Max Value:", max_value)
print("Selected Items:", selected_items)
上述代码实现了0-1背包问题的动态规划解法。通过定义一个二维数组 dp 来存储子问题的最优解，然后使用两层循环遍历所有可能的物品和背包容量组合，计算出每个子问题的最优解。最后，通过回溯找出选择的物品。
在上述示例中，我们测试了一个简单的示例，包含3个物品，每个物品的重量分别为10、20、30，价值分别为60、100、120，背包容量为50。程序输出了最大价值以及选择的物品索引，使用二维数组 dp 来存储子问题的最优解，其中 dp[i][j] 表示在考虑前 i 个物品，且背包容量为 j 的情况下的最优解。通过填充整个 dp 数组，我们可以逐步计算出问题的最优解。
最终的最优解将存储在 dp[n][capacity] 中，其中 n 是物品的总数，capacity 是背包的容量。
背包问题中动态规划算法的核心部分dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])，用于计算子问题的最优解。
dp[i][j] 表示在考虑前 i 个物品，且背包容量为 j 的情况下的最优解，即背包能够装下的物品的最大总价值。
dp[i - 1][j] 表示不选择第 i 个物品时的最优解，即当前背包容量为 j，不考虑第 i 个物品时的最大总价值。
dp[i - 1][j - weights[i - 1]] + values[i - 1] 表示选择第 i 个物品时的最优解，即当前背包容量为 j，考虑第 i 个物品时的最大总价值。weights[i - 1] 是第 i 个物品的重量，values[i - 1] 是第 i 个物品的价值。
所以，这行代码的含义是：选择第 i 个物品时，比较不选择第 i 个物品和选择第 i 个物品的两种情况，取其中的最大值作为当前背包容量为 j 时的最优解。
通过比较这两种情况，我们可以确定是否将第 i 个物品放入背包中，以使得背包的总价值最大化。
回溯具体
从最后一个物品开始，逐步向前回溯。具体的操作如下：
初始化一个空列表 selected_items，用于存储选择的物品的索引。
初始化变量 j 为背包的剩余容量，初始值为总容量 capacity。
使用 for 循环从最后一个物品开始向前遍历，即从 n 到 1，每次减 1。
在每一次循环中，判断当前物品是否被选择。如果 dp[i][j] 不等于 dp[i - 1][j]，说明当前物品被选择放入背包中。
将当前物品的索引 i - 1 添加到 selected_items 列表中，表示选择了该物品。
更新剩余容量 j，减去当前物品的重量 weights[i - 1]。
检查剩余容量 j 是否为 0，如果为 0，则已经没有剩余容量，即背包已经装满，可以终止循环。
循环结束后，selected_items 列表中存储了被选择的物品的索引，即最优解中的物品选择。
通过这样的回溯操作，我们可以找到最优解中选择的物品索引。
经典问题4：矩阵求和
题目主要信息:
给定一个矩阵，从矩阵左上角到右下角，每次只能向下或者向右
从左上角到右下角路径上经过的所有数字之和为路径和，求该路径和的最小值
矩阵不为空，每个元素值都为非负数
具体做法：
step 1：我们可以构造一个与矩阵同样大小的二维辅助数组，其中dp[i][j]表示以(i,j)位置为终点的最短路径和，则dp[0][0]=matrix[0][0]
step 2：很容易知道第一行与第一列，只能分别向右或向下，没有第二种选择，因此第一行只能由其左边的累加，第一列只能由其上面的累加。
step 3：边缘状态构造好以后，遍历矩阵，补全矩阵中每个位置的dp数组值：如果当前的位置是(i，j)，上一步要么是(i−1,j)往下，要么就是(i,j−1)往右，那么取其中较小值与当前位置的值相加就是到当前位置的最小路径和，因此状态转移公式为dp[i][j]=min(dp[i−1][j],dp[i][j−1])+matrix[i][j]
step 4：最后移动到(n−1,m−1)的位置就是到右下角的最短路径和。
def max_Matrix(arr):
rows = len(arr)
cols = len(arr[0])
# dp[i][j]表示以当前i，j位置为终点的最短路径长度
dp = [[0 for _ in range(cols)] for _ in range(rows)]
dp[0][0] = arr[0][0]
# 处理第一行
for j in range(1, cols):
dp[0][j] = arr[0][j] + dp[0][j - 1]
# 处理第一列
for j in range(1, rows):
dp[j][0] = arr[j][0] + dp[j - 1][0]
print(dp)
for i in range(1, rows):
for j in range(1, cols):
if dp[i - 1][j] < dp[i][j - 1]:
dp[i][j] = dp[i - 1][j] + arr[i][j]
else:
dp[i][j] = dp[i][j - 1] + arr[i][j]
return dp[rows - 1][cols - 1]