Linjiayu6
commented
4 years ago 1 - 509. 斐波那契数
同理题 面试题10- I. 斐波那契数列
严格来说, 不算DP, 但理解 重叠子问题的消除方法
F(0) = 0
F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.自底向上: 从最简单方式推理到我们要的答案。
Open Linjiayu6 opened 4 years ago
Linjiayu6
commented
4 years ago 同理题 面试题10- I. 斐波那契数列
严格来说, 不算DP, 但理解 重叠子问题的消除方法
F(0) = 0
F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.自底向上: 从最简单方式推理到我们要的答案。
Linjiayu6
commented
4 years ago 给你一堆硬币, 让你求最小的组合方式, 求解最少用几枚硬币凑出该金额
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1从简单的方式求解, 再找规律, 再确定DP 函数
如果amount = 1 怎么求解? 如果amount = 2 怎么求解? 如果是amount=3 是怎么求解? ...... 直到amount = 11......
其实这个跟斐波那契数一样的道理。
纸币有三种情况，分别是1, 2, 5
那么为了达成 11数值，只可能是从1, 2, 5这个路径来。
同样, 如果是10, 9, 6 也是分别从1, 2,5 这三个路径来的。
所以问题本身是递归树可以解决的。但是因为树有很多重复节点。所以DP帮我们解决重复子树的问题。
其实这个跟斐波那契数一样的道理 F(11) = min(F(11 - 1), F(11 - 2), F(11 - 5)) + 1 或者是这个币种的本身 从F(10) F(9) F(6) 中取最小 + 1 或则例如F(1) 就是有币种1的。
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]
Linjiayu6
commented
4 years ago 思路:
目标: 利润最大 = 卖 - 买
1. 什么时候买? 最低点买入即可 min(_min, current)
2. 什么时候卖? max(_max, current - 最低点)
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)只看眼前利益 见到利益立刻卖掉
# 贪心算法
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 result暴力求解的思路是:
- 手持cash
1. 买stock 此时手持stock
2. 不买, 手持cash
- 手持stock
1. 卖出stock, 得到利润 => 得到利润
2. 不买, 继续手持stock
状态是 手持cash 和 手持stock 能用暴力的 基本上都可以用DP解决
利润 或 cash 初始化从0开始
现金有两个状态: 1. 继续手持 2. 卖出得到更大利益
max(利润 / 手持现金, -持股 + 卖出金额)
# 理解为 max(不操作, 选择卖出)
持股有两个状态: 1. 继续手持 2. 用利润 - 当前股 买入
max(手持股, 利润 - 当前股)
# 理解为 max(不操作, 选择买入)
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]题目问的是什么, 就定义成什么状态。最长上升子序列的长度, 那么子序列长度是状态。
思路: 当前值为x, 从x开始往前找, 直到找到y值, x < y, max(y_n + 1, _max)比较
```python
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)
连续问题 当前一个状态: 我自己 vs 我自己 + 和连续的别人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)思路:
当前的状态是从谁而来的? 往下又如何推动?
两个比较的时候，用DP, 矩阵完美解决问题
- 如果ABC vs AC比较, 那就是 AB 和 A 结果 + 1
- 如果是 ABC vs AB 比较, 那就是 max(AB 和 AB, ABC 和 A)
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]for 状态1 in 状态1所有值:
for 状态2 in 状态2所有值:
for ......
dp[状态1][状态2][...] = 择优(选择1, 选择2, ......)同题 256. 粉刷房子
Linjiayu6
commented
4 years ago 思路: 从word1 => word2 有三个状态可用 插入 / 删除 / 替换
word1 = "horse", word2 = "ros"
- h 替换成 r => rorse
- r 删除 => rose
- e 删除 => ros
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])同类型题但是动态规划超时了
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] == 1输入: "sea", "eat"
输出: 2
解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"
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删除和
Linjiayu6
commented
4 years ago 思路: 小偷无法偷项链房间金额。
状态: 抢 和 不抢
选择: max(自己和 i - 2 存储值, i - 1 存储值)
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]条件: 收尾是挨着的, 不能偷
这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。
同时，相邻的房屋装有相互连通的防盗系统，
如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
目标: 首尾不能同时存在, 那就分开首尾, 单独计算, 最后求解最大值即可。
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)一个个数整理, 最后 数学推理出来 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]class 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
# 看了答案的写法
# 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
动态规则: 求最值问题。运筹学的最优方法。
核心问题是什么呢？求解动态规划的核心问题是穷举。 因为要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值呗
[动态规划三要素] 1. 重叠子问题 2. 最优子结构 3. 状态转移方程
明确问题 => 明确状态 => 明确选择 => 定义DP
先思考“如何穷举(所有解的可能)”，然后再追求“如何聪明地穷举”。