做网站许昌,长沙模板网站建设企业,友点cms,小程序一般需要多少钱70. 爬楼梯#xff08;剑指 Offer 10- II. 青蛙跳台阶问题#xff09;
递归#xff08;英语#xff1a;Recursion#xff09;#xff0c;是指在函数的定义中使用函数自身的方法。有意义的递归通常会把问题分解成规模缩小的同类子问题#xff0c;当子问题缩写到寻常的时…70. 爬楼梯剑指 Offer 10- II. 青蛙跳台阶问题
递归英语Recursion是指在函数的定义中使用函数自身的方法。有意义的递归通常会把问题分解成规模缩小的同类子问题当子问题缩写到寻常的时候我们可以直接知道它的解。然后通过建立递归函数之间的联系转移即可解决原问题。
而记忆化递归就是用数组或者哈希表记录下递归过程中的计算结果避免重复计算。
以爬楼梯为例我们想知道爬 n 阶楼梯的方案数 f(n)由于每次只能爬 1 阶或 2 阶楼梯所以其实如果知道爬 n - 1 阶和 n - 2 阶楼梯的方案数 f(n-1) 和 f(n-2)就能知道爬 n 阶楼梯的方案数 f(n) f(n-1) f(n-2)。 式子中最小为 n-2 根据题意 n-2 0也可以严格大于0区别不大后面相应修改 那么 n 2。意味着最后一次递归调用为 f(2) f(1) f(0)边界就是 f(1) 1f(0) 1。
直接递归的代码如下
class Solution:def climbStairs(self, n: int) - int:if n 1:return 1return self.climbStairs(n - 1) self.climbStairs(n - 2)是会超时的利用记忆化递归可以减少许多重复运算顺利通过
class Solution:memo dict()def climbStairs(self, n: int) - int:if n 1:return 1if n in self.memo:return self.memo[n]self.memo[n] self.climbStairs(n-1) self.climbStairs(n-2)return self.memo[n]思路不难只是用一个字典 memo 记录出现过的台阶与对应的方案数如果有记录的话就不用往下递归了直接返回结果即可。剑指 Offer 的题目区别只在于结果要对 1000000007 取余数。
509. 斐波那契数剑指 Offer 10- I. 斐波那契数列
class Solution:memo dict()def fib(self, n: int) - int:if n 1:return nif n in self.memo:return self.memo[n]self.memo[n] self.fib(n-1) self.fib(n-2)return self.memo[n]求斐波那契数除了边界其余代码都是一样的。
1137. 第 N 个泰波那契数
class Solution:memo dict()def tribonacci(self, n: int) - int:if n 0:return 0if n 1 or n 2:return 1if n in self.memo:return self.memo[n]self.memo[n] self.tribonacci(n-1) self.tribonacci(n-2) self.tribonacci(n-3)return self.memo[n]这题求的是泰波那契数思路基本一样只是递归公式中最小的是 n-3所以 n 3最后一次递归是 n 3若知道 n 0, 1, 2 的值即可得到 n 3 的结果所以递归边界可知。题目其实给了
746. 使用最小花费爬楼梯
class Solution:memo dict()def minCostClimbingStairs(self, cost: List[int]) - int:if len(cost) 1:return 0if len(cost) 2:return min(cost)if tuple(cost) in self.memo:return self.memo[tuple(cost)]self.memo[tuple(cost)] min(cost[0] self.minCostClimbingStairs(cost[1:]), cost[1] self.minCostClimbingStairs(cost[2:]))return self.memo[tuple(cost)]这题注意开始爬楼梯时爬一个台阶是到 cost[0]两个台阶是到 cost[1]而不是 cost[0] 为起点。想要继续使用字典只能用可哈希对象元组不能用数组。
说完记忆化递归我们说说动态规划。动态规划英语Dynamic programming简称DP是通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。若要解一个给定问题我们需要解其不同部分即子问题再根据子问题的解以得出原问题的解。通常许多子问题非常相似为此动态规划法试图仅仅解决每个子问题一次从而减少计算量一旦某个给定子问题的解已经算出则将其记忆化存储以便下次需要同一个子问题解之时直接查表。
我们应该留意到动态规划的核心思路也是通过记忆化避免重复运算实际上动态规划中的 dp 数组状态数组对应的就是记忆化递归中的 memo 字典。关于动态规划的简单入门我推荐这篇知乎文章。
总结来说就是三点定义 dp 数组元素的含义状态是什么、找出 dp 数组元素间的关系式递推公式或状态转移方程、找出初始条件。用上面的例题进行说明
70. 爬楼梯剑指 Offer 10- II. 青蛙跳台阶问题
dp 数组元素 dp[i] 的含义为爬 i 阶楼梯的方案数。 数组元素间的关系由最开始的分析可知dp[i] dp[i-1] dp[i-2]。 初始条件为 dp[1] 1, dp[2] 2注意我这里不讨论 dp[0] 的初始化是因为题目说了 n 不可能为 0所以我的遍历也是从 3 开始的代码如下
class Solution:def climbStairs(self, n: int) - int:if n 1 or n 2:return ndp [0] * (n1)dp[1] 1dp[2] 2for i in range(3, n1):dp[i] dp[i-1] dp[i-2]return dp[-1]509. 斐波那契数剑指 Offer 10- I. 斐波那契数列
class Solution:def fib(self, n: int) - int:if n 0 or n 1:return ndp [0] * (n 1)dp[0] 0dp[1] 1for i in range(2, n 1):dp[i] dp[i - 1] dp[i - 2]return dp[-1]dp[i] 的含义i 对应的斐波那契数
递推公式dp[i] dp[i-1] dp[i-2]
初始条件 dp[0] 0, dp[1] 1
观察到实际上每次都只改变了三个位置所以优化写法如下
class Solution:def fib(self, n: int) - int:if n 0 or n 1:return nf1 0f2 1f3 0for i in range(1, n):f3 f1 f2f1, f2 f2, f3return f31137. 第 N 个泰波那契数
class Solution:def tribonacci(self, n: int) - int:if n 0:return 0if n 2:return 1dp [0] * (n 1)dp[0] 0 dp[1] dp[2] 1for i in range(3, n 1):dp[i] dp[i-3] dp[i-2] dp[i-1]return dp[-1]dp[i] 的含义i 对应的泰波那契数
递推公式dp[i] dp[i-3] dp[i-2] dp[i-1]
初始条件 dp[0] 0, dp[1] 1, dp[2] 1
优化写法
class Solution:def tribonacci(self, n: int) - int:if n 1:return nif n 2:return 1f1 0f2 1f3 1f4 2for i in range(3, n1):f4 f1 f2 f3f1, f2, f3 f2, f3, f4return f4746. 使用最小花费爬楼梯
class Solution:def minCostClimbingStairs(self, cost: List[int]) - int:n len(cost)dp [0] * (n 1)dp[0] cost[0]dp[1] cost[1]for i in range(2, n):dp[i] cost[i] min(dp[i-1], dp[i-2])dp[n] min(dp[n-1], dp[n-2])return dp[n]dp[i] 的含义到达第 i 级台阶时最小的总花费第一步有花费最后一步没花费
递推公式dp[i] cost[i] min(dp[i-1], dp[i-2])
初始条件 dp[0] cost[0], dp[1] cost[1]
由于最后一步没花费所以最后一个元素需要单独求。优化写法
class Solution:def minCostClimbingStairs(self, cost: List[int]) - int:n len(cost)f1 cost[0]f2 cost[1]f3 0for i in range(2, n):f3 cost[i] min(f1, f2)f1, f2 f2, f3f3 min(f1, f2)return f362. 不同路径剑指 Offer II 098. 路径的数目
class Solution:def uniquePaths(self, m: int, n: int) - int:dp [[1 for _ in range(n)] for _ in range(m)]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[m-1][n-1]dp[i][j] 的含义表示从 (0, 0) 出发到 (i, j) 有 dp[i][j] 条不同的路径
递推公式dp[i][j] dp[i-1][j] dp[i][j-1] 只能从上或左到达当前位置
初始条件 dp[i][0]一定都是1因为从 (0, 0) 的位置到 (i, 0) 的路径只有一条dp[0][j]也同理方便起见就将整个 dp 二维数组都初始化为 1
for 循环是 m 和 n因为要返回的就是 dp[m-1][n-1]符合定义。
63. 不同路径 II
class Solution:def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) - int:m len(obstacleGrid)n len(obstacleGrid[0])dp [[0 for _ in range(n)] for _ in range(m)]for i in range(m):if obstacleGrid[i][0] 1:breakelse:dp[i][0] 1for j in range(n):if obstacleGrid[0][j] 1:breakelse:dp[0][j] 1#print(dp)for i in range(1, m):for j in range(1, n):if obstacleGrid[i][j] ! 1:dp[i][j] dp[i-1][j] dp[i][j-1]return dp[m-1][n-1]dp[i][j] 的含义表示从 (0, 0) 出发到 (i, j) 有 dp[i][j] 条不同的路径
递推公式dp[i][j] dp[i-1][j] dp[i][j-1] 前提是当前位置不是障碍
初始条件 先将整个 dp 二维数组都初始化为 0然后 dp[i][0] 第一列在遇到障碍之前都为 1因为从 (0, 0) 的位置到 (i, 0) 的路径只有一条dp[0][j]第一行同理。
64. 最小路径和剑指 Offer II 099. 最小路径之和
class Solution:def minPathSum(self, grid: List[List[int]]) - int:m len(grid)n len(grid[0])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 j in range(1, n):dp[0][j] dp[0][j-1] grid[0][j]for i in range(1, m):for j in range(1, n):dp[i][j] min(dp[i-1][j], dp[i][j-1]) grid[i][j]return dp[m-1][n-1]dp[i][j] 的含义表示从 (0, 0) 出发到 (i, j) 的最小路径之和
递推公式dp[i][j] min(dp[i-1][j], dp[i][j-1]) grid[i][j]
初始条件dp[0][0] 就是 grid[0][0]然后第一列与第一行的最小路径之和都是唯一的就是单纯地累加
931. 下降路径最小和
class Solution:def minFallingPathSum(self, matrix: List[List[int]]) - int:n len(matrix)dp [[0 for _ in range(n)] for _ in range(n)]for j in range(n):dp[0][j] matrix[0][j]for i in range(1, n):for j in range(n):if j 0:dp[i][j] min(dp[i-1][j], dp[i-1][j1]) matrix[i][j]elif j n-1:dp[i][j] min(dp[i-1][j], dp[i-1][j-1]) matrix[i][j]else:dp[i][j] min(dp[i-1][j], dp[i-1][j1], dp[i-1][j-1]) matrix[i][j]return min(dp[-1])dp[i][j] 的含义表示从 (0, 0) 出发到达 (i, j) 的最小路径之和
递推公式 如果在最左边的话路径和就等于正上方和右上方两者中小的路径和加上当前的路径花费 dp[i][j] min(dp[i-1][j], dp[i-1][j1]) matrix[i][j] 如果在最右边的话路径和就等于左上方和正上方两者中小的路径和加上当前的路径花费 dp[i][j] min(dp[i-1][j], dp[i-1][j-1]) matrix[i][j] 如果在中间则路径和就等于左上方、正上方和右上方三者中小的路径和加上当前的路径花费dp[i][j] min(dp[i-1][j], dp[i-1][j1], dp[i-1][j-1]) matrix[i][j]
初始条件dp 数组的第一层等于 matrix 第一层实际上最左边和最右边也可以作为初始化
120. 三角形最小路径和剑指 Offer II 100. 三角形中最小路径之和
class Solution:def minimumTotal(self, triangle: List[List[int]]) - int:n len(triangle)dp []for i in range(1, n1):dp.append([0 for _ in range(i)])dp[0][0] triangle[0][0]for i in range(1, n):for j in range(i1):if j 0:dp[i][j] dp[i-1][j] triangle[i][j]elif j i:dp[i][j] dp[i-1][j-1] triangle[i][j] else:dp[i][j] min(dp[i-1][j], dp[i-1][j-1]) triangle[i][j]return min(dp[-1])dp[i][j] 的含义表示从 (0, 0) 出发到达 (i, j) 的最小路径之和
递推公式 如果在最左边的话路径和就等于正上方的路径和加上当前的路径花费 dp[i][j] dp[i-1][j] triangle[i][j] 如果在最右边的话路径和就等于左上方的路径和加上当前的路径花费 dp[i][j] dp[i-1][j-1] triangle[i][j] 如果在中间则路径和就等于正上方和左上方两者中小的路径和加上当前的路径花费 dp[i][j] min(dp[i-1][j], dp[i-1][j-1]) triangle[i][j]
初始条件dp 数组的第一层等于 triangle 第一层实际上最左边和最右边也可以作为初始化
这题注意 j 的循环次数在第 i 层就循环 i 次
1289. 下降路径最小和 II
困难题我最开始的想法是在上上题的基础上让当前位置最小路径和等于不是当前列的路径和中最小的值再加上当前位置的路径花费
class Solution:def minFallingPathSum(self, grid: List[List[int]]) - int:m, n len(grid), len(grid[0])dp [[0] * n for _ in range(m)]dp[0][:] grid[0][:]for i in range(1, m):for j in range(n):temp float(inf)for k in range(n):if k ! j and dp[i-1][k] temp:temp dp[i-1][k]dp[i][j] temp grid[i][j]return min(dp[-1])但是显然这个方法的时间复杂度是 O(m * n * n)容易超时。换一个思路如果知道了第一层的最小路径那么在第二层除了跟它同一列的位置都是加上这个最小路径为最优那同一列的位置加谁呢第一层中第二小的路径呗。这样实际上就完成了从第一层到第二层的递推dp 数组自然可以构建出来了。
class Solution:def minFallingPathSum(self, grid: List[List[int]]) - int:m, n len(grid), len(grid[0])dp [[0] * n for _ in range(m)]dp[0][:] grid[0][:]for i in range(1, m):# 找到最小的值minflag dp[i-1].index(min(dp[i-1]))# 除了同一列的位置都加上这个最小值for j in range(0, n):if j ! minflag:dp[i][j] grid[i][j] dp[i-1][minflag]# 找到第二小的值if minflag 0:minflag2 min(dp[i-1][1:])elif minflag n - 1:minflag2 min(dp[i-1][:-1])else:minflag2 min(min(dp[i-1][:minflag]), min(dp[i-1][minflag1:]))# 给同一列的位置加上这个第二小的值dp[i][minflag] grid[i][minflag] minflag2return min(dp[-1])343. 整数拆分
class Solution:def integerBreak(self, n: int) - int:dp [0 for _ in range(n1)]dp[2] 1for i in range(3, n1):for j in range(1, i):# 假设对正整数 i 拆分出的第一个正整数是 j1 j i则有以下两种方案# 1) 将 i 拆分成 j 和 i−j 的和且 i−j 不再拆分成多个正整数此时的乘积是 j * (i-j)# 2) 将 i 拆分成 j 和 i−j 的和且 i−j 继续拆分成多个正整数此时的乘积是 j * dp[i-j]dp[i] max(dp[i], j * (i - j), j * dp[i - j])return dp[n]dp[i] 的含义表示分拆数字 i可以得到的最大乘积为 dp[i]
递推公式dp[i] max(dp[i], j * (i - j), j * dp[i - j])
初始条件dp[2] 1dp[0] dp[1] 不应该初始化因为没有意义
96. 不同的二叉搜索树
class Solution:def numTrees(self, n: int) - int:dp [0 for _ in range(n1)]dp[0] 1for i in range(1, n1):for j in range(1, i1):dp[i] dp[j-1] * dp[i-j]return dp[n]dp[i] 的含义1到 i 为节点组成的二叉搜索树的个数为 dp[i]
递推公式dp[i] dp[j-1] * dp[i-j]
初始条件dp[0] 1
当 n 1 时dp[1] 1当 n 2 时dp[2] 2当 n 3 时左右子树可能的数量分别为20、11、02这对应了 dp[3] dp[2] * dp[0] dp[1] * dp[1] dp[0] * dp[2]后面的以此类推。
