算法学习之动态规划
程序员文章站
2024-03-17 17:14:34
...
动态规划
主要思想
若要解一个给定问题,我们需要解其不同部分(即子问题),再根据子问题的解以得出原问题的解。动态规划往往用于优化递归问题,例如斐波那契数列,如果运用递归的方式来求解会重复计算很多相同的子问题,利用动态规划的思想可以减少计算量。
动态规划法仅仅解决每个子问题一次,具有天然剪枝的功能,从而减少计算量,
一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个子问题解之时直接查表。
动态规划模板步骤:
- 确定动态规划状态
- 写出状态转移方程(画出状态转移表)
- 考虑初始化条件
- 考虑输出状态
- 考虑对时间,空间复杂度的优化(Bonus)
Leetcode300.最长上升子序列
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
#先将特殊情况排除
if not nums:
return 0
#设置dp的初始状态
dp = [1] * len(nums)
#动态方程
for i in range(len(nums)):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i],dp[j]+1)
return max(dp)
leetcode674.最长连续递增序列
class Solution:
def findLengthOfLCIS(self, nums: List[int]) -> int:
if not nums:
return 0
dp = [1] * len(nums)
for i in range(len(nums)-1):
if nums[i+1] > nums[i]:
dp[i+1] = dp[i] + 1
return max(dp)
leetcode5.最长回文子串
len1 = len(s)
if len1 < 2:
return s
dp = [[False for i in range(len1)]for i in range(len1)]
max_len = 1
start = 0
for j in range(1,len1):
for i in range(j):
if s[i] == s[j]:
if j - i < 3:
dp[i][j] = True
else:
dp[i][j] = dp[i+1][j-1]
if dp[i][j]:
current_len = j - i + 1
if current_len > max_len:
max_len = current_len
start = i
return s[start:start+max_len]
leetcode516.最长回文子序列
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
len1 = len(s)
if len1 == 0:
return 0
if len1 == 1:
return 1
dp = [[0 for i in range(len1)]for i in range(len1)]
for i in range(len1):
dp[i][i] = 1
max_len = 1
for i in range(len1,-1,-1):
for j in range(i+1,len1):
if s[i] == s[j]:
dp[i][j] = dp[i+1][j-1] + 2
else:
dp[i][j] = max(dp[i][j-1],dp[i+1][j])
return dp[0][-1]
leetcode72.编辑距离
def minDistance(self, word1, word2):
#m,n 表示两个字符串的长度
m=len(word1)
n=len(word2)
#构建二维数组来存储子问题
dp=[[0 for _ in range(n+1)] for _ in range(m+1)]
#考虑边界条件,第一行和第一列的条件
for i in range(n+1):
dp[0][i]=i #对于第一行,每次操作都是前一次操作基础上增加一个单位的操作
for j in range(m+1):
dp[j][0]=j #对于第一列也一样,所以应该是1,2,3,4,5...
for i in range(1,m+1): #对其他情况进行填充
for j in range(1,n+1):
if word1[i-1]==word2[j-1]: #当最后一个字符相等的时候,就不会产生任何操作代价,所以与dp[i-1][j-1]一样
dp[i][j]=dp[i-1][j-1]
else:
dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1 #分别对应删除,添加和替换操作
return dp[-1][-1] #返回最终状态就是所求最小的编辑距离
leetcode198.打家劫舍
class Solution:
def rob(self, nums: List[int]) -> int:
len1 = len(nums)
if not nums:
return 0
if len1 == 1:
return nums[0]
dp = [0] * len1
dp[0] = nums[0]
if nums[1]<dp[0]:
dp[1] = nums[0]
else:
dp[1] = nums[1]
for i in range(2,len1):
dp[i] = max(dp[i-1],dp[i-2] + nums[i])
return max(dp)
leetcode213.打家劫舍2
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums:
return 0
elif len(nums)<=2:
return max(nums)
def helper(nums):
if len(nums)<=2:
return max(nums)
dp=[0]*len(nums)
dp[0]=nums[0]
dp[1]=max(nums[0],nums[1])
for i in range(2,len(nums)):
dp[i]=max(dp[i-1],dp[i-2]+nums[i])
return dp[-1]
return max(helper(nums[1:]),helper(nums[:-1]))
上一篇: 查找算法:顺序查找、二分查找、分块查找
下一篇: leetcode学习一之动态规划(DP)