动态规划（Dynamic Programming）
动态规划（Dynamic Programming）是一种常用的算法设计技术，用于解决具有最优子结构性质和重叠子问题的问题。它通过将原问题分解为若干个子问题，并先求解子问题的最优解，然后利用子问题的最优解构建原问题的最优解。
动态规划算法通常包括以下几个关键步骤：
-
定义状态：将原问题划分为若干个子问题，并定义合适的状态表示问题的特征和限制条件。
-
确定状态转移方程：通过分析问题的特点和限制条件，找出子问题之间的关系，建立状态之间的转移方程。这个方程描述了问题的最优解与子问题的最优解之间的关系。
-
初始化边界条件：确定初始阶段的状态值，以及初始阶段到下一阶段的状态转移。
-
通过状态转移方程求解：根据状态转移方程，从初始阶段开始，逐个计算每个阶段的状态值，直到求解出最终的目标状态。
-
根据最终状态得出结果：根据最终的目标状态，得出问题的最优解。
动态规划算法通常使用动态规划表或一维/二维数组来存储子问题的解，以减少重复计算，提高算法的效率。
动态规划算法可以解决很多问题，如最短路径问题、背包问题、最长公共子序列问题等。它在实际应用中具有广泛的应用，能够有效地解决一些复杂的优化问题。
常见算法题
1.最短路径问题
最短路径问题是动态规划算法的一个经典应用，其中最著名的算法是Dijkstra算法。以下是Dijkstra算法的Python实现示例：
import heapq
def dijkstra(graph, start):
# 初始化距离字典，用于存储起点到各个顶点的最短距离
distances = {vertex: float('inf') for vertex in graph}
distances[start] = 0
# 初始化优先队列，用于选择距离最短的顶点
heap = [(0, start)]
while heap:
# 弹出当前距离最短的顶点
current_distance, current_vertex = heapq.heappop(heap)
# 如果当前距离大于已记录的最短距离，则跳过
if current_distance > distances[current_vertex]:
continue
# 遍历当前顶点的邻居顶点
for neighbor, weight in graph[current_vertex].items():
distance = current_distance + weight
# 如果通过当前顶点到达邻居顶点的距离更短，则更新最短距离
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(heap, (distance, neighbor))
return distances
使用示例：
# 定义有向加权图
graph = {
'A': {'B': 5, 'C': 2},
'B': {'D': 4, 'E': 2},
'C': {'B': 8, 'E': 7},
'D': {'E': 6, 'F': 3},
'E': {'F': 1},
'F': {}
}
start_vertex = 'A'
distances = dijkstra(graph, start_vertex)
print(f"从顶点 {start_vertex} 出发到各个顶点的最短距离：")
for vertex, distance in distances.items():
print(f"顶点 {vertex}: {distance}")
输出结果：
从顶点 A 出发到各个顶点的最短距离：
顶点 A: 0
顶点 B: 5
顶点 C: 2
顶点 D: 9
顶点 E: 7
顶点 F: 8
以上是Dijkstra算法的Python实现示例，用于求解最短路径问题。该算法通过不断选择距离最短的顶点，更新起点到各个顶点的最短距离，直到找到最短路径。
2.背包问题
背包问题是动态规划算法的经典应用之一。以下是背包问题的动态规划算法的Python实现示例：
def knapsack(weights, values, max_weight):
n = len(weights)
dp = [[0] * (max_weight + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, max_weight + 1):
if weights[i - 1] <= j:
dp[i][j] = max(dp[i - 1][j], values[i - 1] + dp[i - 1][j - weights[i - 1]])
else:
dp[i][j] = dp[i - 1][j]
return dp[n][max_weight]
使用示例：
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
max_weight = 8
max_value = knapsack(weights, values, max_weight)
print("背包能容纳的最大价值为:", max_value)
输出结果：
背包能容纳的最大价值为: 10
以上代码实现了一个动态规划算法来解决背包问题。
在算法中，我们使用一个二维数组dp来保存子问题的解，
其中dp[i][j]表示前i个物品在背包容量为j时的最大价值。
通过遍历物品和背包容量，根据动态规划的状态转移方程逐步计算出最优解。
最终返回dp[n][max_weight]即可得到背包能容纳的最大价值。
3. 爬楼梯（Climbing Stairs）：
- 题目描述：假设你正在爬楼梯，每次只能爬一步或两步。请问，爬到第n阶楼梯有多少种不同的方法？
- 示例代码：
def climbStairs(n):
if n <= 2:
return n
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 2
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
爬楼梯问题是动态规划中的经典问题，假设有n阶楼梯，每次可以爬1阶或2阶，问有多少种不同的方法可以爬到n阶。
这个问题可以用递归和动态规划两种方法来解决，下面先介绍递归方法：
递归方法：我们可以先假设有f(n)种方法爬到n阶，那么爬到n-1阶就有f(n-1)种方法，爬到n-2阶就有f(n-2)种方法，而爬到n阶只有两种情况，一种是从n-1阶爬一阶上来，另一种是从n-2阶爬两阶上来，所以f(n)=f(n-1)+f(n-2)，这就是递归关系式。
def climbStairs(n):
if n <= 2:
return n
return climbStairs(n - 1) + climbStairs(n - 2)
动态规划方法：动态规划方法和递归方法的思想是一样的，只是实现方式不同。在动态规划方法中，我们从底层开始逐步求解，而不是像递归方法那样从顶层开始求解。
首先定义一个数组dp，其中dp[i]表示爬到第i阶有多少种方法。根据递归关系式，我们可以得到状态转移方程为dp[i]=dp[i-1]+dp[i-2]，即爬到第i阶的方法数等于爬到第i-1阶的方法数加上爬到第i-2阶的方法数。
接下来我们从底层开始逐步求解，先求出dp[1]和dp[2]，然后根据状态转移方程逐步求出dp[3]、dp[4]、dp[5]…直到dp[n]。最后dp[n]就是我们要求的结果，即爬到第n阶有多少种方法。文章来源：https://www.toymoban.com/news/detail-732504.html
无论是递归方法还是动态规划方法，时间复杂度都是O(n)，空间复杂度都是O(n)，因此两种方法的时间和空间复杂度都是相同的。文章来源地址https://www.toymoban.com/news/detail-732504.html
4. 最长公共子序列（Longest Common Subsequence）：
- 题目描述：给定两个字符串text1和text2，找到它们的最长公共子序列的长度。
- 示例代码：
def longestCommonSubsequence(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
5. 买卖股票的最佳时机（Best Time to Buy and Sell Stock）：
- 题目描述：给定一个数组，它的第i个元素是一支给定股票第i天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。
- 示例代码：
def maxProfit(prices):
buy1, buy2 = float('-inf'), float('-inf')
sell1, sell2 = 0, 0
for price in prices:
sell2 = max(sell2, buy2 + price)
buy2 = max(buy2, sell1 - price)
sell1 = max(sell1, buy1 + price)
buy1 = max(buy1, -price)
return sell2
6. 编辑距离（Edit Distance）：
- 题目描述：给定两个单词word1和word2，计算出将word1转换成word2所使用的最少操作次数。可以对一个单词进行插入、删除或替换操作。
- 示例代码：
def minDistance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
return dp[m][n]
到了这里，关于动态规划的算法题以及其python实现的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
