动态规划-leetcode

写在前面:感谢引文,https://labuladong.gitbook.io/algo/

 

具体来说,动态规划的一般流程就是三步:暴力的递归解法 -> 带备忘录的递归解法 -> 迭代的动态规划解法

就思考流程来说,就分为一下几步:找到状态和选择 -> 明确 dp 数组/函数的定义 -> 寻找状态之间的关系

下面三种分类

一、线性规划

二、区间规划

以上两种,一般问题形式是:【统计 】or 【最优解

三、约束规划


送你两套编码模板~

1、【模板一】一维双循环

dp = [0]*n;

for i in range(n):
    for j in range(i,n):
        dp[i] = 最值(dp[i], dp[j] + ...)
    

 

2、【模板二】二维双循环

dp = [0]*n;

for i in range(n) :
    for j in range(i,n) :
        if (arr[i] == arr[j]) 
            dp[i][j] = dp[i][j] + ...
        else
            dp[i][j] = 最值(...)
    

 

 


 

爬楼梯/跳台阶(leetcode第70题)

打家劫舍(leecode第198题)

记忆点:单层循环  f(i) = max{ dp(i-1), nums[i-1] + dp(i-2) }

def rob(nums):
    if len(nums) == 0:
        return 0
    N = len(nums)
    dp = [0] * (N+1)
    dp[0] = 0
    dp[1] = nums[0]
    for k in range(2, N+1):
        dp[k] = max(dp[k-1], nums[k-1] + dp[k-2])
    return dp[N]

 

最长上升子序列  (leetcode第300题)

记忆点:模板一

def lengthOfLIS(nums):
    if not nums:
        return 0
    dp = []
    for i in range(len(nums)):
        dp.append(1)
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

 

最长公共子序列  (leetcode第1143题)

记忆点:模板二

def longestCommonSubsequence(str1, str2):
    m, n = len(str1), len(str2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    # 进行状态转移
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if str1[i - 1] == str2[j - 1]:
                # 找到一个 lcs 中的字符
                dp[i][j] = 1 + dp[i - 1][j - 1]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[-1][-1]

 

最长回文子序列  (leetcode第516题)

记忆点:模板二,从左下到右上遍历

def longestPalindromeSubseq(str):
    n = len(s)
    dp = [[0] * n for i in range(n)]    
    for i in range(n):
        dp[i][i] = 1
    # 倒着遍历
    for i in range(n, -1, -1):
        for j in range(i + 1, n):
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    return dp[0][n - 1]

 

网格路径数  (leetcode第62题)

记忆点:左+上,dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

def uniquePaths(m,n):
    dp = [[1] * n] + [[1] + [0] * (n - 1) for _ in range(m - 1)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    return dp[-1][-1]

 

 

零钱兑换  (leetcode第322题)

记忆点:双for从钱遍历

def coinChange(coins, amount):
    dp = [0] * (amount + 1)
    dp[0] = 1

    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]
    return dp[amount]

 

0-1背包

记忆点:经典的模板二

def knapsack(w,v,C):
	#初始化带横纵序列的二维数组
	mem = [[0]*C+1]*len(w)+1
	for i in range(1,C+1):mem[i,0]=i
	for i in range(1,len(w)+1):mem[0,i]=i
	#开始遍历
	for i in range(1,len(w)+1):
		for j in range(1,C+1):
			if w[i-1]<=j : #如果第i件物品能放下
				mem[i][j]=max(mem[i][j],mem[i-1][j],mem[i-1][j-w[i-1]]+v[i-1]) 
			else:
				mem[i][j]=mem[i-1][j]
	return mem[-1,-1]	

 

编辑距离

记忆点:经典的模板二

def minDistance(word1, word2):
        m,n = len(word1),len(word2)
	#初始化带横纵序列的二维数组
        mem = [[0]*(n+1)]*(m+1)        
        for i in range(m+1):mem[i][0]=i
        for i in range(n+1):mem[0][i]=i
       	#开始遍历
        for i in range(1,m+1):
            for j in range(1,n+1):
                if word1[i-1]==word2[j-1]:
                    mem[i][j] = min(mem[i-1][j]+1,mem[i][j-1]+1,mem[i-1][j-1])
                else:
                    mem[i][j] = min(mem[i-1][j]+1,mem[i][j-1]+1,mem[i-1][j-1]+1)        
        return mem[-1][-1]
2

发表评论

电子邮件地址不会被公开。 必填项已用*标注

微信扫一扫

微信扫一扫

微信扫一扫,分享到朋友圈

动态规划-leetcode
嘿!有什么能帮到您的吗?
返回顶部

显示

忘记密码?

显示

显示

获取验证码

Close