网站开发项目付款方式,随州网站制作价格,珠宝网站制作的理念,dede网站图标动态规划#xff08;记忆化搜索#xff09;#xff1a; 将给定问题划分成若干子问题#xff0c;直到子问题可以被直接解决。然后把子问题的答保存下来以免重复计算#xff0c;然后根据子问题反推出原问题解的方法 动态规划也称为递推#xff08;暴力深搜记忆中间状态结果… 动态规划记忆化搜索 将给定问题划分成若干子问题直到子问题可以被直接解决。然后把子问题的答保存下来以免重复计算然后根据子问题反推出原问题解的方法 动态规划也称为递推暴力深搜记忆中间状态结果其中
递推公式 dfs向下递归的公式递推列表的初始值 递归的边界 文章目录 一、爬楼梯思路解题方法记忆化搜索的复杂度传统搜索的复杂度 二、三角形最小路径和思路思路解题方法传统搜索的复杂度记忆化搜索的复杂度 三、大盗阿福思路解题方法复杂度 一、爬楼梯 Problem One: 70. 爬楼梯 题目描述 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢 输入: 输入一个整数表示台阶数 n 输出: 返回一个整数表示爬到楼顶的方案数。 思路
对第一级台阶方案数等于1对第二级台阶方案数为2直接迈两级或迈两次一级对于第i级台阶(i 3)来说它的前驱台阶可能是i-1也可能是i-2所以从第0阶台阶上到第i阶台阶的方案数等于上到第i-1阶台阶的方案数加上上到第i-2阶台阶的方案数。
解题方法
创建一个dp[]列表存储到达每一级台阶的方案数使用for循环从小到大逐步求出所有台阶对应的方案数最后返回dp[n-1]即可
记忆化搜索的复杂度
时间复杂度: O ( n ) O(n) O(n) 空间复杂度: O ( n ) O(n) O(n) class Solution:def climbStairs(self, n: int) - int:if n 0:return 0elif n 1:return 1dp [0]*(n1)dp[0], dp[1], dp[2] 0, 1, 2for i in range(3, n1):dp[i] dp[i-1] dp[i-2]return dp[-1]根据 动态规划 记忆化搜索 的理念可知本题可以直接使用暴力搜索完成但算法的复杂度有明显差异。
传统搜索的复杂度
时间复杂度: O ( 2 n ) O(2^n) O(2n) 空间复杂度: O ( 1 ) O(1) O(1) # 使用DFS直接搜索
# 时间复杂度:O(2的n次方)
def f(n)-int:if n 0:return 0elif n 1:return 1elif n 2:return 2else :return f(n-1)f(n-2)print(f(int(input())))二、三角形最小路径和 Problem Two: LCR 100. 三角形最小路径和 题目描述 给定一个三角形 triangle 找出自顶向下的最小路径和。 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 1 的两个结点。也就是说如果正位于当前行的下标 i 那么下一步可以移动到下一行的下标 i 或 i 1 。 输入: 输入一个二维列表表示三角形 例如triangle [[2],[3,4],[6,5,7],[4,1,8,3]] 输出: 返回一个整数表示最小路径和。 思路
对第一级台阶方案数等于1对第二级台阶方案数为2直接迈两级或迈两次一级对于第i级台阶(i 3)来说它的前驱台阶可能是i-1也可能是i-2所以从第0阶台阶上到第i阶台阶的方案数等于上到第i-1阶台阶的方案数加上上到第i-2阶台阶的方案数。
思路
题目是一个标准的深度优先搜索问题因为每一层中的元素会多次被使用所以可以通过创建列表存储到达该点所需要的最小路径和记忆化搜索的方式提升效率。记忆化搜索也就是动态规划。
解题方法
自然的方法是自上而下找出每一层各元素到三角形上顶点的最小路径和然后在最后一层中选出最小路径。但这种方法中每一层的元素需要分成左端点、中间节点和右端点三类最后还需要遍历一整行找出最小值算法的时间复杂度较高。
最左侧的节点前驱节点只能是tri[i-1][0]最右侧的节点前驱节点只能是tri[i-1][i-1]中间的节点 前驱节点可以是tri[i-1][j] or tri[i-1][j1]
传统搜索的复杂度
时间复杂度: O ( n 2 ) O(n^2) O(n2) 空间复杂度: O ( n ) O(n) O(n) # 自上而下计算最小和
def f()-int:# 读取输入n int(input())tri []for i in range(n):tri.append([int(j) for j in input().split()])# 算法主体if not tri:# 如果列表为空返回0return 0rows len(tri)dp []# 第一行特殊处理dp.append([tri[0][0]])for i in range(1, rows):temp []for j in range(i1):if j 0:temp.append(tri[i][0]dp[i-1][0])elif j i:temp.append(tri[i][j]min(dp[i-1][j-1], dp[i-1][j]))else:temp.append(tri[i][j]dp[i-1][j-1])dp.append(temp)return min(dp[-1])
print(f())算法优化 通过对题目的观察可知题目不要求找出最短路径中的每一个元素所以也可以自下而上的查找存储每一个元素到最后一层的最小路径和。这样每一层只有一种节点前驱节点一定是 tri[i1][j] 和 tri[i1][j1] 二选一不必区分左右端点而且最后只需返回dp[0][0]即可因为dp[0][0]存储的就是三角形上顶点到三角形最下层的最小路径和。
记忆化搜索的复杂度
时间复杂度: O ( n 2 ) O(n^2) O(n2) 空间复杂度: O ( n ) O(n) O(n) # 除了自上而下的计算还可以自下而上地求出dp列表的值
# 在自下而上的过程中三角形每一层都只有一种节点更为简单
def f()-int:n int(input())tri []for i in range(n):tri.append([int(j) for j in input().split()])# 算法主体# 创建dp列表dp tri[:]for row in range(n-2, -1, -1):for col in range(row1):dp[row][col] min(dp[row1][col], dp[row1][col1]) tri[row][col]return dp[0][0]print(f())三、大盗阿福 Problem Three: 信息学奥赛一本通 1301. 大盗阿福 题目描述 阿福是一名经验丰富的大盗。趁着月黑风高阿福打算今晚洗劫一条街上的店铺。 这条街上一共有 N 家店铺每家店中都有一些现金。阿福事先调查得知只有当他同时洗劫了两家相邻的店铺时街上的报警系统才会启动然后警察就会蜂拥而至。 作为一向谨慎作案的大盗阿福不愿意冒着被警察追捕的风险行窃。他想知道在不惊动警察的情况下他今晚最多可以得到多少现金 输入: 输入的第一行是一个整数T(T≤50) 表示一共有T组数据。 接下来的每组数据第一行是一个整数N(1≤N≤100,000) 表示一共有N家店铺。第二行是N个被空格分开的正整数表示每一家店铺中的现金数量。每家店铺中的现金数量均不超过1000。 输出: 对于每组数据输出一行。该行包含一个整数表示阿福在不惊动警察的情况下可以得到的现金数量。 思路
分析可知被选中的两家店之间可能间隔1家店也可能间隔2家店但不可能间隔大于等于3家店因为间隔的三家店中中间的那一家也可以同时被选中如果不选则该方案一定不是最优方案。所以本题实质上与爬楼梯相似都是典型的动态规划题目。
解题方法
创建一个列表dp记录从左向右打劫到每一个店铺时所能获得的最大金额最后dp中的最大值即为所求。
第一家店铺最大金额等于该店铺的钱数第二家店铺最大金额等于 max(money[0], money[1])第三家店铺最大金额等于 max(money[1], money[0]money[2])第ii 3家店铺最大金额等于 money[i-1] max(dp[i-2], dp[i-3])
复杂度
时间复杂度: O ( n ) O(n) O(n) 空间复杂度: O ( n ) O(n) O(n) def f(n, money):# n len(money)if n 1:print(money[0])return elif n 2:print(max(money))returnelif n 3:print(max(money[1], money[0]money[2]))return# 初始化dp列表dp [0]*ndp[0] money[0]dp[1] max(money[0], money[1])dp[2] max(money[1], money[0] money[2])for i in range(3, n):dp[i] money[i] max(dp[i-2], dp[i-3])print(max(dp))t int(input())
for i in range(t):f(int(input()), [int(k) for k in input().split()])
