斐波那契数列
动态规划
- 递归超出复杂度，原因是重复计算了太多f(n-2)
- 使用列表dp来记录，避免重复计算，直接通过idnex取出值即可
class Solution:
def fib(self, n: int) -> int:
# stop case
if n == 0:
return 0
if n == 1:
return 1
# recursion
# return self.fib(n-1) + self.fib(n-2)
else:
dp = [0,1]
for i in range(2,n+1):
tmp = (dp[i-2]+dp[i-1]) % 1000000007
dp.append(tmp)
return dp[n]
矩阵快速幂
image.png
- 通过计算矩阵[[1,1],[1,0]]的n次幂，可以快速计算
- 直接求取复杂度为O(n)，快速幂算法O(logn)
class Solution:
def fib(self, n: int) -> int:
MOD = 10 ** 9 + 7
if n < 2:
return n
def multiply(a: List[List[int]], b: List[List[int]]) -> List[List[int]]:
c = [[0, 0], [0, 0]]
for i in range(2):
for j in range(2):
c[i][j] = (a[i][0] * b[0][j] + a[i][1] * b[1][j]) % MOD
return c
def matrix_pow(a: List[List[int]], n: int) -> List[List[int]]:
ret = [[1, 0], [0, 1]]
while n > 0:
if n & 1:
ret = multiply(ret, a)
n >>= 1
a = multiply(a, a)
return ret
res = matrix_pow([[1, 1], [1, 0]], n - 1)
return res[0][0]
青蛙跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
- stop case: 跳上第0级台阶只有1种方法；跳上第1级台阶只有1种方法；
- 递归：跳上第n级台阶的方法 = 跳上第n-2级台阶的方法 + 跳上第n-1级台阶的方法
class Solution:
def numWays(self, n: int) -> int:
# stop case
if n == 0:
return 1
if n == 1:
return 1
else:
dp = [1,1]
for i in range(2,n+1):
tmp = (dp[i-2]+dp[i-1]) % 1000000007
dp.append(tmp)
return dp[n]
另有矩阵快速幂算法
股票的最大利润
假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
动态规划
- dp[i] 截止至第i天可以获得的最大利润
- dp[i] = max(dp[i-1] ， 如果今天卖出的最大利润)
- dp[i] = max(dp[i-1], price[i] - min(price[0:i]))
优化 min(price[0:i])
- 使用lowest变量来储存最小价格，循环比较更新
优化dp列表
- 由于第i项只和 i-1、current price、lowest price相关，可以不使用列表
- profit储存结果：profit=max(profit,prices[i]−min(cost,prices[i])
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if prices:
# 初始化
profit = 0
cur_price = 0
lowest = prices[0]
for i in range(len(prices)):
cur_price = prices[i]
# 更新lowest price
lowest = min(lowest,cur_price)
# 更新 profit
# 取最大： 上一次的profit， 本次卖出(当前价-最低)
profit = max(profit, cur_price - lowest)
return profit
return 0
连续子数组的最大和
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
- dp[i] 代表以元素 nums[i] 为结尾的连续子数组最大和。(由此来确认递归的子数组连续性）
- 如果 dp[i-1] ≤0 ，说明加上它还不如不要它；即 dp[i] = num[i]
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
if nums:
# 初始化dp list
dp = [nums[0]]
max_sum = nums[0]
for i in range(1,len(nums)):
if dp[i-1] >= 0:
dp.append(dp[i-1] + nums[i])
max_sum = max(max_sum,dp[i])
if dp[i-1]<0:
dp.append(nums[i])
max_sum = max(max_sum,dp[i])
return max_sum
极简-原有list叠加更改
- 同上，nums[i] 表示以元素 nums[i] 为结尾的连续子数组最大和
- 依次叠加 max{dp[i-1],0}
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
for i in range(1,len(nums)):
nums[i] += max(0,nums[i-1])
return max(nums)
二维数组拿礼物最大价值
- 只能往右/下走，也就是可以考虑 dp[i-1][j] 和 dp[i][j-1]
-
特殊case 包括 i=0 & j=0; i=0; j=0
image.png
class Solution:
def maxValue(self, grid: List[List[int]]) -> int:
# dp[i,j] = max(dp[i-1,j],dp[i,j-1]) + list[i][j]
for i in range(len(grid)):
for j in range(len(grid[0])):
if i ==0 and j == 0:
continue
elif i == 0:
grid[i][j] += grid[i][j-1]
elif j == 0:
grid[i][j] += grid[i-1][j]
else:
grid[i][j] += max(grid[i][j-1],grid[i-1][j])
return grid[-1][-1]
把数字翻译成字符串
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
*问题的关键是当前的这个数，只能以它本身去做翻译，还是可以连着上一个来一起翻译
- 对于s[i]，需要确认 s[i-1:i+1] 这两个字符是否可以翻译 （<=25并>=10）
- 如果可以，dp[i] = dp[n-1] + dp[n-2] （可以单独翻译，也可以作为二位数翻译）
- 如果不可以，只能单独翻译，也就是dp[i] = dp[n-1]
class Solution:
def translateNum(self, num: int) -> int:
# dp[n]，前n个数字能翻译的方法
# 如果这两位合法：
# dp[n] = dp[n-1] + dp[n-2]
# 如果不合法：
# dp[n] = dp[n-1]
dp = [1]
s = str(num)
for i in range(1,len(s)):
temp = s[i-1:i+1]
if temp <= "25" and temp >= "10":
if i > 1:
dp.append(dp[i-1] + dp[i-2])
else:
dp.append(2)
else:
dp.append(dp[i-1])
return dp[-1]
最长不含重复字符的子字符串
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
- 动态规划 dp[i]表示以s[i]结尾的不重复最长子串长度
- 对于cur字符 s[i]，截取左半部分，s[:i]，使用rfind去找和他一样的重复元素，其index为dup_index
- 如果dup_index = -1， 无相同字符，dp[j] = dp[j]+1
- i-1- dp[i-1]为以s[i-1]结尾的最长不重复子串的开头index
- 如果start_index > dup_index，这个重复元素不影响，正常的把当前元素加上去，长度为dp[i] = dp[i-1] + 1
- 如果start_index <= dup_index，这个重复元素导致dp[i-1]不能直接使用，最长的不重复长度为i - dup_index
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
if not s:
return 0
dp = [1]
for i in range(1,len(s)):
dup_index = s[:i].rfind(s[i])
if dup_index == -1:
# 没有重复的，直接dp[i-1] + 1
dp.append(dp[i-1] + 1)
else:
start_index = i-1- dp[i-1]
if start_index > dup_index:
# 不影响，正常+1
dp.append(dp[i-1] + 1)
else:
dp.append(i-dup_index)
return max(dp)
剪绳子
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]k[1]...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
- f(n) : 长度为n的绳子的最大乘积 （至少剪一下）
- f(n)第一下有n-1种剪法，也就是在 1,2,...n-1 处来一刀。-> 设这个位置为i
- 剩下的还有n-i长，如果继续剪，它最大乘积为f(n-i)；如果不剪，它最大乘积为n-i，
- 因此： f(n) = max[ i * max[f(n-i), n-1]] for i in 1,2,3, ... ,n
class Solution:
def cuttingRope(self, n: int) -> int:
# 初始化dp
dp = [1] * (n+1) # 因为最终返回dp[n]，总长度需要n+1
for i in range(2,n+1): # 从2开始进行动态规划
for first in range(1,i): # 对于长度为i的绳子，第一刀剪下1,2,3,...i-1
# 剪第一刀，分成 first , n-first
dp[i] = max( dp[i] , first * max(dp[i - first], i-first))
return dp[n]
