动态规划和记忆化递归一般都是可以相互转化的
- 动态规划的dp表就相当于递归中的缓存
- 动态规划中的状态转移方程式就相当于递归调用
下面我们就拿几道题目来实际感受下
1、面试题14- I. 剪绳子
自顶向下的记忆化递归
class Solution(object):
def cuttingRope(self, n):
"""
:type n: int
:rtype: int
"""
def memo(sub_n):
# 如果该n值已经计算过，则直接返回缓存值
if f[sub_n] != 0:
return f[sub_n]
# 结束条件
if sub_n == 2:
return 1
rst = 1
# 对每一个子数进行处理
for i in range(1, sub_n):
# 比较再次分割（即递归）和不分割的乘积
rst = max(rst, max(memo(sub_n - i) * i,
i * (sub_n - i)))
f[sub_n] = rst
return rst
# 结果列表(缓存)
f = [0] * (n + 1)
return memo(n)
自底向上的动态规划
class Solution(object):
def cuttingRope(self, n):
"""
:type n: int
:rtype: int
"""
if n <= 2:
return 1
# 初始化dp状态
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 1
# 遍历并更新状态值：
# 因为需要求的是长度为n的值，所以状态值有n个，
# 对于每一个状态值，都需要遍历其子状态以便得到其最大值
# 因此这里需要二层循环
for i in range(3, n+1):
for j in range(1, i):
# 状态转移方程式: 绳子长度为i时，比较再次分割和不分割的乘积
dp[i] = max(dp[i], max(dp[i-j] * j, (i - j) * j))
return dp[n]2、面试题47. 礼物的最大价值
自顶向下的记忆化递归
# coding: utf-8
class Solution(object):
def maxValue(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
if not grid:
return 0
# 如果是单行
m = len(grid)
if m == 1:
return sum(grid[0])
# 如果是单列
n = len(grid[0])
if n == 1:
return sum([row[0] for row in grid])
def memo(i, j):
# 如果该坐标点已经计算过，则直接取值
if f[i][j] != 0:
return f[i][j]
# 递归结束条件：注意这里的边界处理
if i == 0 and j == 0:
return grid[0][0]
elif i == 0:
return memo(0, j - 1) + grid[0][j]
elif j == 0:
return memo(i - 1, 0) + grid[i][0]
# 要知道当前坐标值，就需要知道前一个坐标值
# 即自顶向下的递归
rst = max(memo(i - 1, j), memo(i, j - 1)) + grid[i][j]
# 将结果值缓存，避免重复计算
f[i][j] = rst
return rst
# 结果列表（缓存）
f = [[0 for _ in range(n)] for _ in range(m)]
return memo(m - 1, n - 1)
自底向上的动态规划
class Solution(object):
def maxValue(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
if not grid:
return 0
# 如果是单行
m = len(grid)
if m == 1:
return sum(grid[0])
# 如果是单列
n = len(grid[0])
if n == 1:
return sum([row[0] for row in grid])
# dp状态初始化
dp = [[0 for _ in range(n)] for _ in range(m)]
dp[0][0] = grid[0][0]
# 为啥我们这里需要这样初始化呢？
# 这个从后面的状态转移方程式就可以知道
for i in range(1, m):
dp[i][0] = dp[i-1][0] + grid[i][0]
for i in range(1, n):
dp[0][i] = dp[0][i-1] + grid[0][i]
# 状态遍历，因为是需要从左上角到右下角，因此需要状态就是m，n的遍历
# 即需要两层循环
for i in range(1, m):
for j in range(1, n):
# 状态转移方程式：题目规定了只能往右走和向下走，
# 因此到某个坐标只有两种情况，比对两种情况的最大值即可
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
return dp[m - 1][n - 1]3、面试题63. 股票的最大利润
自顶向下的记忆化递归
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if not prices:
return 0
n = len(prices)
def memo(i):
# 如果已经计算过了该天的利润，直接返回即可
if f[i] != 0:
return f[i]
# 递归结束条件
if i == 0:
return 0
# 要知道当天的利润，就需要知道前一天的利益并比较，即需要递归前一天
# 这就是自顶向下的递归
rst = max(memo(i - 1), prices[i] - min(prices[:i]))
# 返回结果值
f[i] = rst
return rst
# 结果列表（缓存）
f = [0 for _ in range(n)]
return memo(n - 1)自底向上的动态规划
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if not prices:
return 0
n = len(prices)
# 初始化状态
dp = [0 for _ in range(n)]
dp[0] = 0
# 遍历状态
for i in range(1, n):
# 状态转移方程：对比当天卖出（之前买入的最小值）跟当天不卖出的利润
dp[i] = max(prices[i] - min(prices[:i]), dp[i - 1])
return dp[n - 1]
评论 (2)
