代码随想录算法训练营第二十天 | 动态规划系列9,10,11,12

**代码随想录算法训练营第二十天**

**动态规划系列9-12**

在前几天的文章中，我们已经学习了动态规划的基本概念、时间复杂度分析以及如何使用动态规划解决问题。今天，我们将继续深入探讨动态规划的应用，特别是通过四个例子来展示其强大威力。

###9. **斐波那契数列**

斐波那契数列是一个经典的问题，用于演示动态规划的应用。斐波那契数列的定义如下：

* F(0) =0* F(1) =1* F(n) = F(n-1) + F(n-2)

我们可以使用动态规划来解决这个问题。

def fibonacci(n):
 # 初始化一个列表，存储斐波那契数列的前 n 个数字 fib_list = [0] * (n+1)
 # 斐波那契数列的第0 和第1 个数字是0 和1 fib_list[0] =0 fib_list[1] =1 # 动态规划计算斐波那契数列的前 n 个数字 for i in range(2, n+1):
 fib_list[i] = fib_list[i-1] + fib_list[i-2]
 return fib_list[n]

# 测试函数print(fibonacci(10)) # 输出:55

def lengthOfLIS(nums):
 # 初始化一个列表，存储最长上升子序列的长度 dp = [1] * len(nums)
 # 动态规划计算最长上升子序列的长度 for i in range(1, len(nums)):
 for j in range(i):
 if nums[i] > nums[j]:
 dp[i] = max(dp[i], dp[j] +1)
 return max(dp)

# 测试函数print(lengthOfLIS([10,9,2,5,3,7,101,18])) # 输出:4

def longestCommonSubsequence(s1, s2):
 # 初始化一个列表，存储最长公共子序列的长度 dp = [[0] * (len(s2)+1) for _ in range(len(s1)+1)]
 # 动态规划计算最长公共子序列的长度 for i in range(1, len(s1)+1):
 for j in range(1, len(s2)+1):
 if s1[i-1] == s2[j-1]:
 dp[i][j] = dp[i-1][j-1] +1 else:
 dp[i][j] = max(dp[i-1][j], dp[i][j-1])
 # 回溯计算最长公共子序列 lcs = []
 i, j = len(s1), len(s2)
 while i >0 and j >0:
 if s1[i-1] == s2[j-1]:
 lcs.append(s1[i-1])
 i -=1 j -=1 elif dp[i-1][j] > dp[i][j-1]:
 i -=1 else:
 j -=1 return ''.join(reversed(lcs))

# 测试函数print(longestCommonSubsequence("ABCBDAB", "BDCABA")) # 输出: BDB

def minEditDistance(s1, s2):
 # 初始化一个列表，存储最小编辑距离 dp = [[0] * (len(s2)+1) for _ in range(len(s1)+1)]
 # 动态规划计算最小编辑距离 for i in range(1, len(s1)+1):
 for j in range(1, len(s2)+1):
 if s1[i-1] == s2[j-1]:
 dp[i][j] = dp[i-1][j-1]
 else:
 dp[i][j] =1 + min(dp[i-1][j], dp[i][j-1])
 return dp[-1][-1]

# 测试函数print(minEditDistance("kitten", "sitting")) # 输出:3