[动态规划 Dynamic Programming] #1
Comments
1 - 509. 斐波那契数同理题 面试题10- I. 斐波那契数列 自底向上: 从最简单方式推理到我们要的答案。 |
2 - 322. 零钱兑换
其实这个跟斐波那契数一样的道理 class Solution(object):
def coinChange(self, coins, amount):
if len(coins) == 0: return -1
if amount <= 0: return 0
"""
如果是[1, 3, 5] 结果是8
只可能从 7, 5, 3 三个路径来, 求他们的最小 + 1 或 是纸币的本身的倍数 或 -1
if 匹配不上 -1
else 匹配的上 min( min(F(7), F(5), F(3)) + 1, amount / coin本身 )
"""
F = [-1]
for money in range(1, amount + 1): # 从1元开始, 直到 计算的值
tmp = []
for coin in coins: # 遍历纸币, 要得知他们最小的
rest = money - coin
if rest > 1 and F[rest] != -1:
tmp.append(F[rest] + 1) # 该纸币1 + 上一个最小值状态
if money % coin == 0: # 可以被整除 或者是 纸币本身
tmp.append(money / coin)
data = -1 if len(tmp) == 0 else min(tmp)
F.append(data)
return F[-1]
|
3 - 121. 买卖股票的最佳时机只能买入卖出一次, 只需要找最低点和最高点即可
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
# 同 121. 买卖股票的最佳时机
_len = len(prices)
if _len == 0 or _len == 1: return 0
_min, _max = prices[0], 0
for i in range(1, _len):
current = prices[i]
_min = min(_min, current)
_max = max(_max, current - _min)
return max(_max, 0) |
4 - *122. 买卖股票的最佳时机 II DP / 贪心算法1. 贪心算法 局部最优
# 贪心算法
class Solution(object):
def maxProfit(self, prices):
_len = len(prices)
if _len == 0 or _len == 1: return 0
result = 0
for i in range(1, _len):
result += max(prices[i] - prices[i - 1], 0)
return result2. 动态规划 - 状态 和 状态转移
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# 动态规划算法
_len = len(prices)
if _len == 0 or _len == 1: return 0
cash, stock = [0], [0 - prices[0]]
for i in range(1, _len):
# prices[i] 当前股市价格
cash.append(max(cash[i - 1], stock[i - 1] + prices[i]))
stock.append(max(stock[i - 1], cash[i - 1] - prices[i]))
return cash[-1] |
状态和状态转移
|
5 - 300. 最长上升子序列题目问的是什么, 就定义成什么状态。最长上升子序列的长度, 那么子序列长度是状态。
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
_len = len(nums)
if _len == 0 or _len == 1: return _len
temp = [1]
for i in range(1, _len):
_max = 1
for j in range(i - 1, -1,-1):
if nums[i] > nums[j]: _max = max(temp[j] + 1, _max)
temp.append(_max)
return max(temp) |
6 - 53. 最大子序和
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
_len = len(nums)
if _len == 0: return 0
if _len == 1: return nums[0]
# 这道题, 最核心问题是 连续!!!
tmp = nums[0] # 连续tmp
result = nums[0] # 最大值保存
for i in range(1, _len):
temp_max = max(nums[i], nums[i] + tmp)
tmp = nums[i] if temp_max == nums[i] else nums[i] + tmp
result = max(result, temp_max)
return resultnums = [-2,1]
var maxSubArray = function(nums) {
if (nums.length === 1) return nums[0]
var _max = 0
var _sequence = nums.shift()
for (num of nums) {
// 我num 还是 我 + 连续 num + _sequence
var temp = Math.max(num + _sequence, num)
// 如果我最大 则 重新赋值我, 如果是连续最大是连续问题
_sequence = temp === num ? num : num + _sequence
_max = Math.max(_max, _sequence)
}
return _max
};
maxSubArray(nums) |
7 - 1143. 最长公共子序列 DP Table
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
len1, len2 = len(text1), len(text2)
if len1 == 0 or len2 == 0: return 0
# 创建矩阵
# matrix = []
# for i in range(len2 + 1): # 多补一圈0
# line = []
# for j in range(len1 + 1): # 多补一圈0
# line.append(0)
# matrix.append(line)
matrix = [[0] * (len1 + 1) for _ in range(len2 + 1)]
for i in range(1, len2 + 1):
for j in range(1, len1 + 1):
if text2[i-1: i] == text1[j-1: j]:
matrix[i][j] = matrix[i - 1][j - 1] + 1
else:
# matrix[i][j] = max(matrix[i - 1][j - 1], matrix[i - 1][j], matrix[i][j - 1])
matrix[i][j] = max(matrix[i - 1][j], matrix[i][j - 1])
return matrix[len2][len1] |
DP 套路 [状态] 对应 [选择]
for 状态1 in 状态1所有值:
for 状态2 in 状态2所有值:
for ......
dp[状态1][状态2][...] = 择优(选择1, 选择2, ......)同题 256. 粉刷房子 |
8 - 72. 编辑距离 🔥
import numpy as np
class Solution(object):
def minDistance(self, word1, word2):
m, n = len(word1), len(word2)
if m == 0 or n == 0:
return max(m, n)
# matrix = np.zeros(shape = (n + 1, m + 1))
matrix = [[0] * (m + 1) for _ in xrange(n + 1)]
# 建立矩阵
for i in range(1, m + 1): # 1 ~ m
matrix[0][i] = i
for j in range(1, n + 1): # 1 ~ n
matrix[j][0] = j
"""
[
[0. 1. 2. 3. 4. 5.]
[1. 0. 0. 0. 0. 0.]
[2. 0. 0. 0. 0. 0.]
[3. 0. 0. 0. 0. 0.]
]
"""
for i in range(1, n + 1):
for j in range(1, m + 1):
if word1[j - 1] == word2[i - 1]:
matrix[i][j] = matrix[i - 1][j - 1]
else:
min1 = matrix[i][j - 1] + 1
min2 = matrix[i - 1][j] + 1
min3 = matrix[i - 1][j - 1] + 1
matrix[i][j] = min(min1, min2, min3)
return int(matrix[n][m])161. 相隔为 1 的编辑距离同类型题但是动态规划超时了 class Solution:
def isOneEditDistance(self, s: str, t: str) -> bool:
s_len, t_len = len(s), len(t)
if s_len == 0:
return True if t_len == 1 else False
if t_len == 0:
return True if s_len == 1 else False
# 创建矩阵
matrix = [ [0] * (s_len + 1) for _ in range(t_len + 1)]
# 初始化矩阵边界值, 如果当s为空, t操作数, 反之亦然
for i in range(1, s_len + 1): matrix[0][i] = i
for j in range(1, t_len + 1): matrix[j][0] = j
"""
[
[0. 1. 2.]
[1. 0. 0.]
[2. 0. 0.]
[3. 0. 0.]
]
"""
for x in range(1, t_len + 1):
for y in range(1, s_len + 1):
if s[y-1: y] == t[x-1: x]: # 值相同
matrix[x][y] = matrix[x-1][y-1] # 问题转化成上一步问题
else:
matrix[x][y] = 1 + min(
matrix[x-1][y-1],
matrix[x][y-1],
matrix[x-1][y]
)
return matrix[t_len][s_len] == 1583. 两个字符串的删除操作只删除将两个字符串变相同 ps: 不能 替代 或 插入
class Solution(object):
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
m, n = len(word1), len(word2)
if m == 0 or n == 0: return max(m, n)
# 建立矩阵
matrix = [[0] * (m + 1) for _ in range(n + 1)]
# 边界值处理
for i in range(1, m + 1): matrix[0][i] = i
for j in range(1, n + 1): matrix[j][0] = j
for i in range(1, n + 1):
for j in range(1, m + 1):
if word1[j - 1] == word2[i - 1]: # 第几个字符相同
matrix[i][j] = matrix[i - 1][j - 1]
else:
# 只能删除, 这里和上面有所不同
matrix[i][j] = 1 + min(matrix[i - 1][j], matrix[i][j - 1])
return matrix[n][m]同类型题 712. 两个字符串的最小ASCII删除和 |
9 - 198. 打家劫舍 I
class Solution:
def rob(self, nums: List[int]) -> int:
_len = len(nums)
if _len == 0: return 0
if _len == 1: return nums[0]
if _len == 2: return max(nums)
tempList = [nums[0], nums[0]] if nums[0] >= nums[1] else [nums[0], nums[1]]
i = 2
while i < _len:
data = max(tempList[i - 1], tempList[i - 2] + nums[i])
tempList.append(data)
i += 1
return tempList[-1]213. 打家劫舍 II 未独立计算条件: 收尾是挨着的, 不能偷
class Solution:
def handle (self, nums):
List = []
if nums[0] >= nums[1]: List = [nums[0], nums[0]]
else: List = [nums[0], nums[1]]
for i in range(2, len(nums)):
data = max(List[i - 1], List[i -2] + nums[i])
List.append(data)
return List[-1]
def rob(self, nums: List[int]) -> int:
# 最后判断是取倒数第一个值还是第二个
if len(nums) == 0: return 0 # 不能偷 因为是个环
if len(nums) == 1: return nums[0]
if len(nums) == 2: return max(nums)
# 是个环, 收尾不能同时存在, 那就分开求个最大值即可
noend = self.handle(nums[0: len(nums)-1]) # 没有尾部
nostart = self.handle(nums[1: len(nums)]) # 没有首都
return max(noend, nostart) |
10 - 剑指 Offer 14- I. 剪绳子一个个数整理, 最后 数学推理出来 F[n - 3] * 3 是最大
- n = n1 + n2 + ....
- 最大值 = n1 * n2 * n3 * .....
幂运算是指数爆炸形式的。
例如: 6
2 + 2 + 2 => 2 ^ 3 = 8
3 + 3 => 3 ^ 2 = 9
例如: 9
2 + 2 + 2 + 3 = 2 ^ 3 * 3 = 24
3 + 3 + 3 = 3 ^ 3 = 27
例如: 11
5 + 6 => 5 ^ 6 = 30
3 + 3 + 3 + 2 => 3 ^ 3 * 2 = 54
# 1 - 动态规划计算: 当 n > 3: F(n - 3) * 3
# 2- 或 直接幂运算
当 n % 3 == 0: 可以被整除 结果为3的n // 3 次幂 pow(3, n // 3)
当 n % 3 == 1: pow(3, n // 3 - 1) * 4 (eg: 10 3 * 3 * 3 * 1 < 3 * 3 * 4)
当 n % 3 == 2: pow(3, n // 3) * 2 (eg: 8 3 * 3 * 2)
最后得出结论是 3的次幂运算是保证乘积最大的
# 第一版
class Solution(object):
def cuttingRope(self, n):
"""
:type n: int
:rtype: int
"""
if n == 0 or n == 1: return 0
if n == 2: return 1
F = [0, 0, 1]
for i in range(3, n + 1):
half = int(i / 2)
_max = half * (half + 1) if i % 2 == 1 else half * half
for j in range(2, half + 1):
_max = max(_max, F[i - j] * j)
F.append(_max)
return F[-1]# 第二版简化版本
class Solution(object):
def cuttingRope(self, n):
"""
:type n: int
:rtype: int
"""
if n == 0 or n == 1: return 0
if n == 2: return 1
F = [0, 0, 1, 2, 4, 6, 9, 12]
if n >= 8:
for i in range(8, n + 1): F.append(F[i - 3] * 3)
return F[n]剑指 Offer 14- II. 剪绳子 IIclass Solution(object):
def cuttingRope(self, n):
"""
:type n: int
:rtype: int
"""
if n == 2: return 1
F = [0, 0, 1, 2, 4, 6, 9, 12, 18, 27]
if n < 10: return F[n]
for i in range(10, n + 1):
F.append(F[i - 3] * 3)
return F[-1] % 1000000007 |
剑指 Offer 49. 丑数同 264. 丑数 II
# 看了答案的写法
# a, b, c 三个指针判断, 是要怎么选择
# L[a] * 2, L[b] * 3, L[c] * 5
class Solution(object):
def nthUglyNumber(self, n):
"""
:type n: int
:rtype: int
"""
if n == 0: return 0
if n == 1: return 1
a, b, c = 0, 0, 0 # 代表三个位置
L = [1] * n
for i in range(1, n):
n1, n2, n3 = L[a] * 2, L[b] * 3, L[c] * 5
_min = min(n1, n2, n3)
L[i] = _min
if n1 == _min: a += 1
if n2 == _min: b += 1
if n3 == _min: c += 1
return L[-1]# 超时了
class Solution(object):
def nthUglyNumber(self, n):
"""
:type n: int
:rtype: int
"""
if n == 0: return 0
if n == 1: return 1
dictionary = { }
num, L = 1, []
while True:
if len(L) == n: return L[-1]
if num in dictionary or num == 1:
L.append(num)
dictionary[num * 2] = num * 2
dictionary[num * 3] = num * 3
dictionary[num * 5] = num * 5
num += 1 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
动态规则: 求最值问题。运筹学的最优方法。
核心问题是什么呢？求解动态规划的核心问题是穷举。
因为要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值呗
[动态规划三要素]
1. 重叠子问题
2. 最优子结构
3. 状态转移方程
明确问题 => 明确状态 => 明确选择 => 定义DP
先思考“如何穷举(所有解的可能)”，然后再追求“如何聪明地穷举”。
The text was updated successfully, but these errors were encountered: