Article directory
- Dynamic Programming
- Common algorithm questions
-
- 1. Shortest path problem
- 2. Backpack problem
- 3. Climbing Stairs:
- 4. Longest Common Subsequence:
- 5. Best Time to Buy and Sell Stock:
- 6. Edit Distance:
Dynamic Programming
Dynamic Programming is a commonly used algorithm design technique for solving problems with optimal substructure properties and overlapping subproblems. It decomposes the original problem into several sub-problems, first solves the optimal solution of the sub-problem, and then uses the optimal solution of the sub-problem to construct the optimal solution of the original problem.
Dynamic programming algorithms usually include the following key steps:
-
Define states: Divide the original problem into several sub-problems, and define appropriate states to represent the characteristics and constraints of the problem.
-
Determine the state transition equation: By analyzing the characteristics and constraints of the problem, find the relationship between sub-problems and establish the transition equation between states. This equation describes the relationship between the optimal solution to the problem and the optimal solutions to the subproblems.
-
Initialization boundary conditions: determine the state value of the initial stage and the state transition from the initial stage to the next stage.
-
Solve through the state transition equation: According to the state transition equation, starting from the initial stage, calculate the state value of each stage one by one until the final target state is solved.
-
Get the result based on the final state: Get the optimal solution to the problem based on the final goal state.
Dynamic programming algorithms usually use dynamic programming tables or one-dimensional/two-dimensional arrays to store solutions to sub-problems to reduce repeated calculations and improve the efficiency of the algorithm.
Dynamic programming algorithms can solve many problems, such as the shortest path problem, the knapsack problem, the longest common subsequence problem, etc. It has a wide range of applications in practical applications and can effectively solve some complex optimization problems.
Common algorithm questions
1. Shortest path problem
The shortest path problem is a classic application of dynamic programming algorithms, the most famous of which is Dijkstra’s algorithm. The following is an example Python implementation of Dijkstra’s algorithm:
import heapq
def dijkstra(graph, start):
# Initialize the distance dictionary, used to store the shortest distance from the starting point to each vertex
distances = {<!-- -->vertex: float('inf') for vertex in graph}
distances[start] = 0
# Initialize the priority queue to select the vertex with the shortest distance
heap = [(0, start)]
while heap:
# Pop up the vertex with the shortest current distance
current_distance, current_vertex = heapq.heappop(heap)
# If the current distance is greater than the shortest distance recorded, skip
if current_distance > distances[current_vertex]:
continue
# Traverse the neighbor vertices of the current vertex
for neighbor, weight in graph[current_vertex].items():
distance = current_distance + weight
# If the distance to the neighbor vertex through the current vertex is shorter, update the shortest distance
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(heap, (distance, neighbor))
return distances
Usage example:
# Define directed weighted graph
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"The shortest distance from vertex {<!-- -->start_vertex} to each vertex:")
for vertex, distance in distances.items():
print(f"Vertex {<!-- -->vertex}: {<!-- -->distance}")
Output result:
The shortest distance from vertex A to each vertex: Vertex A: 0 Vertex B: 5 Vertex C: 2 Vertex D: 9 Vertex E: 7 Vertex F: 8
The above is an example of a Python implementation of Dijkstra’s algorithm, used to solve the shortest path problem. This algorithm continuously selects the vertex with the shortest distance and updates the shortest distance from the starting point to each vertex until the shortest path is found.
2. Backpack problem
The knapsack problem is one of the classic applications of dynamic programming algorithms. The following is an example Python implementation of the dynamic programming algorithm for the knapsack problem:
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]
Usage example:
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
max_weight = 8
max_value = knapsack(weights, values, max_weight)
print("The maximum value that the backpack can hold is:", max_value)
Output result:
The maximum value that the backpack can hold is: 10
The above code implements a dynamic programming algorithm to solve the knapsack problem.
In the algorithm, we use a two-dimensional array dp to save the solution of the sub-problem,
Among them, dp[i][j] represents the maximum value of the first i items when the backpack capacity is j.
By traversing the items and backpack capacity, the optimal solution is gradually calculated based on the state transition equation of dynamic programming.
Finally return dp[n][max_weight] to get the maximum value that the backpack can hold.
3. Climbing Stairs:
- Problem description: Suppose you are climbing stairs and can only take one or two steps at a time. How many different ways are there to climb to the nth step of stairs?
- Sample code:
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]
The stair climbing problem is a classic problem in dynamic programming. Assume that there are n steps, and you can climb 1 or 2 steps each time. How many different ways can you climb to n steps?
This problem can be solved using two methods: recursion and dynamic programming. The recursive method is introduced below:
Recursive method: We can first assume that there are f(n) ways to climb to level n, then there are f(n-1) ways to climb to level n-1, and to climb to level n-2 There are f(n-2) ways, and there are only two ways to climb to level n. One is to climb up one level from level n-1, and the other is to climb up two steps from level n-2, so f (n)=f(n-1) + f(n-2), this is the recursive relationship.
def climbStairs(n):
if n <= 2:
return n
return climbStairs(n - 1) + climbStairs(n - 2)
Dynamic programming method: The idea of dynamic programming method and recursive method is the same, but the implementation method is different. In the dynamic programming method, we start from the bottom and solve step by step instead of starting from the top like the recursive method.
First define an array dp, where dp[i] represents how many ways there are to climb to the i-th level. According to the recursive relationship, we can get the state transition equation as dp[i]=dp[i-1] + dp[i-2], that is, the number of ways to climb to the i-th level is equal to the number of ways to climb to the i-1th level number plus the number of ways to climb to the i-2th level.
Next, we start from the bottom to solve step by step, first find dp[1] and dp[2], and then gradually find dp[3], dp[4], dp[5]… until dp[n] according to the state transition equation . Finally, dp[n] is the result we require, that is, how many ways are there to climb to the nth level.
Whether it is the recursive method or the dynamic programming method, the time complexity is O(n) and the space complexity is O(n), so the time and space complexity of the two methods are the same.
4. Longest Common Subsequence:
- Problem description: Given two strings text1 and text2, find the length of their longest common subsequence.
- Sample code:
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:
- Problem description: Given an array, its i-th element is the price of a given stock on the i-th day. Design an algorithm to calculate the maximum profit you can make. You can complete up to two transactions.
- Sample code:
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:
- Problem description: Given two words word1 and word2, calculate the minimum number of operations used to convert word1 into word2. A word can be inserted, deleted or replaced.
- Sample code:
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]
