🤡前言🤡
好久不见，万分想念呀小伙伴们。 今天才发现一个惊天的动地的事，现在写的是百练成钢还是百炼成钢来着？😫大意了没有闪。无论怎么叫吧都是一个意思,多加练习练就钢一样的写代码能力。不出亿外的话这是百练成钢系列中的最后一篇博客了，出意外的话还会再出几篇。再来重新说一下百练成钢系列的含义吧。百练成钢就是通过一些简单的算法题，让我们的编程技巧更加熟练，达到一个锻炼我们自己编程能力的目的。😤一定要记得百练成钢或者是百炼成钢，可不是摆烂成钢。今天要说的是动态规划这个专题。然后分享几道动态规划入门题。大佬的话可以绕道了。💤
💟什么是动态规划?💞
💗概念💗
动态规划(Dynamic Programming)是-种分阶段求解决策问题的数学思想,它通过把原问题分解为简单的子问题来解决复杂问题动态规划在很多领域都有着广泛的应用,例如管理学,经济学数学,生物学.该类问题又称为DP
动态规划适用于解决带有最优子结构和子问题重叠性质的问题.
最优子结构:
即是局部最优解能够决定全局最优解(也可以认为是问题可以被分解为子问题来解决)，如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质.
子问题重叠:
即是当使用递归进行自顶向下的求解时,每次产生的子问题不总是新的问题,而是已经被重复计算过的问题动态规划利用了这种性质,使用一个集合将已经计算过的结果放入其中当再次遇见重复的问题时，只需要从集合中取出对应的结果.
相信了解过分治算法的同学会发现.动态规划与分治算法很相似,下面我们例举出一些它们的相同之处与不同之处.
相同点:
分治算法与动态规划都是将一个复杂问题分解为简单的子问题.
分治算法与动态规划都只能解决带有最优子结构性质的问题.
不同点
分治算法一般都是使用递归自顶向下实现,动态规划使用迭代自底向上实现或带有记忆功能的递归实现.
动态规划解决带有子问题重叠性质的问题效率更加高效.
分治算法分解的子问题是相对独立的.
动态规划分解的子问题是互相带有关联且有重叠的.
我眼中的DP
DP分类有很多种，解题的思想也很奇妙，感兴趣的可以自行系统学习一下。
DP可以拿一少部分空间去为你的程序争取大量时间。
DP灰常的灵活,你应该弄清相邻的子问题之间的关系，或者说间隔n个子问题之间的关系。
💗通用解题步骤💗
- 设计状态
- 写出状态转移方程
- 设定初始状态
- 执行状态转移
💟练习题💞
💟再谈前缀和、差分、前缀后缀最值
💝问题描述
这几个问题一定不陌生了吧，这是几个问题的求解方式就是线性动态规划效果的集中体现
可以细细感受一下，是不是使用一些特定的方法之后可以为你的程序节约非常大时间。
如果这几个问题还不会的话可以翻一番百练成钢系列中的博文，有详尽的介绍。
我认为想要入门动态规划，需要先将标题上的三个问题进行解决掉。😋
💝问题分析
解决该类问题需要弄清前面求解出来的子问题对后面要求解的大问题有什么帮助（影响）
有帮助的话就记录下来，为后续的求解节省时间。
💝代码实现
'''代码的话可以自己回忆一下，如果忘记了就去看看本专栏其他的博文。'''
💟加泰罗尼亚数列
💝问题描述
在组合数学中，加泰罗尼亚数形成一系列自然数，这些自然数出现在几个通常是递归的计数问题中。它们以比利时数学家 Eugène Charles Catalan (1814–1894) 的名字命名。应用二项式系数从以下公式获得加泰罗尼亚语的第 n 个数：
解释：第一项为1，后面的第n+1项为前n项前后相乘再相加
比如有求第11项，则c11=c10*c0+c9*c1…+c6*c5+c5*c6+…c0*c10
💝问题分析
本题涉及到递推公式，所以可以使用分治方法求解、也可以使用动态规划
如果进行分治的话，每次都要求解一定数量的子问题，非常浪费时间
所以我们可以使用动态规划进行求解，因为求出来的第n项cn对后来的求解会有帮助，节省我们的时间
💝代码实现
# 递归求解（会进行很多次重复计算） # def GTLNY(n): # if n<=1: # return 1 # ans=0 # for i in range(1,n): # ans+=GTLNY(i)*GTLNY(n-i) # return ans # print(GTLNY(10)) n=int(input()) arr=[0]*(n+1) arr[1]=1 for i in range(2,n+1): for j in range(1,i): arr[i]+=arr[j]*arr[i-j] print(arr)
💟将每个元素替换为右侧最大元素
💝问题描述
给你一个数组 arr ，请你将每个元素用它右边最大的元素替换，如果是最后一个元素，用 -1 替换。
完成所有替换操作后，请你返回这个数组。
示例 1：
输入：arr = [17,18,5,4,6,1]
输出：[18,6,6,6,1,-1]
解释：
下标 0 的元素 --> 右侧最大元素是下标 1 的元素 (18)
下标 1 的元素 --> 右侧最大元素是下标 4 的元素 (6)
下标 2 的元素 --> 右侧最大元素是下标 4 的元素 (6)
下标 3 的元素 --> 右侧最大元素是下标 4 的元素 (6)
下标 4 的元素 --> 右侧最大元素是下标 5 的元素 (1)
下标 5 的元素 --> 右侧没有其他元素，替换为 -1
示例 2：
输入：arr = [400]
输出：[-1]
解释：下标 0 的元素右侧没有其他元素。
提示：
1 <= arr.length <= 104
1 <= arr[i] <= 105
💝问题分析
数据量较大的话，每次都需要进行寻找会很浪费时间时间复杂度为o(n2)
所以我们可以使用一些空间将时间换出来，可以先求解一下每个位置的后缀最值
然后对比前一位置后缀最值与该位置数据的大小关系即可求得想要的结果。
转移方程为：ans[i]=max(ans[i+1],arr[i+1])
💝代码实现
arr=list(map(int,input().split(','))) n=len(arr) ans=[0]*n ans[n-1]=arr[n-1] for i in range(n-2,-1,-1): ans[i]=max(ans[i+1],arr[i+1]) ans[n-1]=-1 print(ans)
💟数字三角形
💝问题描述
数字三角形：
给定一个由 n行数字组成的数字三角形如下图所示。
试设计一个算法，计算出从三角形 的顶至底的一条路径(每一步可沿左斜线向下或右斜线向下)，使该路径经过的数字总和最大。
输入格式:
输入有n+1行：
第 1 行是数字三角形的行数 n，1<=n<=100。
接下来 n行是数字三角形各行中的数字。所有数字在0…99 之间。
输出格式:
输出最大路径的值。
输入样例:
在这里给出一组输入。例如：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出样例:
在这里给出相应的输出。例如：
30
💝问题分析
这个题目比较简单，刚开始给的是一个树形图，看起来很恐怖
但是当我们发现将其抽象到二维数组内之后就有了思路，定义一个二维数组用于存储每一个
点的最大路径之和，然后依次求解上一个子问题
在这里我进行了一下分类（边缘单独处理否则就使用else里面的状态转移方程）
由此求出了每一个点的最大路径之和。最后求出ans矩阵最后一行数据的最大值即可
思考一下：能够求最大值，那能不能求最小值呢？最大值、最小值路径呢？
💝代码实现
# 最大和 n=int(input()) a=[[0 for i in range(n)] for j in range(n)] ans=[[0 for i in range(n)] for j in range(n)] for i in range(0,n): temp=list(map(int,input().split())) for j in range(0,i+1): a[i][j]=temp[j] ans[0][0]=a[0][0] ans[0][1]=a[0][0] for i in range(1,n): for j in range(i+1): if j==0: ans[i][0]=a[i][0]+ans[i-1][0] elif j==i: ans[i][j]=ans[i-1][j-1]+a[i][j] else: ans[i][j]=max(ans[i-1][j],ans[i-1][j-1])+a[i][j] print(max(ans[n-1])) # 找出最大和路径（输出各元素即可） ansi=n-1 ansj=ans[n-1].index(max(ans[n-1])) ansls=[] ansls.append(a[ansi][ansj]) for i in range(ansi,0,-1): if ansj!=0: temp=max(ans[i-1][ansj-1],ans[i-1][ansj]) ansj=ans[i-1].index(temp) ansls.append(a[i-1][ansj]) else: ansls.append(ans[i][0]) print(ansls[::-1]) # 最小和 n=int(input()) a=[[0 for i in range(n)] for j in range(n)] ans=[[0 for i in range(n)] for j in range(n)] for i in range(0,n): temp=list(map(int,input().split())) for j in range(0,i+1): a[i][j]=temp[j] ans[0][0]=a[0][0] ans[0][1]=a[0][0] for i in range(1,n): for j in range(i+1): if j==0: ans[i][0]=a[i][0]+ans[i-1][0] elif j==i: ans[i][j]=ans[i-1][j-1]+a[i][j] else: ans[i][j]=min(ans[i-1][j],ans[i-1][j-1])+a[i][j] # print(min(ans[n-1])) # 最小和路径 ansi=n-1 ansj=ans[n-1].index(min(ans[n-1])) # print(ans,ansi,ansj) ansls=[] ansls.append(a[ansi][ansj]) for i in range(ansi,0,-1): if ansj==0: ansls.append(a[i-1][0]) elif ansj==i: ansls.append(a[i-1][ansj-1]) ansj-=1 else: ansj=ans[i-1].index(min(ans[i-1][ansj],ans[i-1][ansj-1])) ansls.append(a[i-1][ansj]) print(ansls[::-1])
💟爬楼梯
💝问题描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1 阶 + 1 阶
2 阶
示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1 阶 + 1 阶 + 1 阶
1 阶 + 2 阶
2 阶 + 1 阶
提示：
1 <= n <= 45
💝问题分析
这个问题也是入门动态规划必做的一个入门题之一，如果不使用动态规划的话
求解起来相当费脑细胞，或者会让初学者无从下手，将本问题可以细化为求解子问题的问题
比如我要上n个台阶,那么我上n阶台阶的方案数应为n-1+n-2阶的总和（因为我不是从n-1上n阶就是从n-2阶上）
由此问题也就得到了解决。
状态转移方程为：ls[i]=ls[i-1]+ls[i-2]
💝代码实现
n=int(input()) ls=[0]*n if n>=2: ls[0]=1 ls[1]=2 for i in range(2,n): ls[i]=ls[i-1]+ls[i-2] elif n==1: ls[0]=1 print(ls[n-1])
💟使用最小花费爬楼梯
💝问题描述
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。
一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例 1：
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。
示例 2：
输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。
提示：
2 <= cost.length <= 1000
0 <= cost[i] <= 999
💝问题分析
这个问题在爬楼梯问题上进行了一点点进化，也就是说你要爬楼梯的时候需要支付一定的费用
怎么样才能保证你爬n阶楼梯费用最少呢？应该是你上第n阶楼梯要么从n-1阶要么从n-2阶
只要应从n-1与n-2阶楼梯中选出最小花费的一个,才使得爬n阶楼梯花费最小，对于每一阶楼梯都是如此；
状态转移方程为：dp[i]=min(dp[i-1],dp[i-2])+cost[i]
💝代码实现
# 有n个楼梯 n=int(input()) # 花费数组 cost=[int(i) for i in input().split(',')] dp=[0]*n if n==1: dp[0]=cost[0] else: dp[0]=cost[0] dp[1]=cost[1] for i in range(2,n): dp[i]=min(dp[i-1],dp[i-2])+cost[i] print(min(dp[n-1],dp[n-2]))
💟打家劫舍
💝问题描述
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，
影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
提示：
[2,1,1,2]
1 <= nums.length <= 100
0 <= nums[i] <= 400
💝问题分析
在取数的时候，不可以取相邻的，所以第n个位置取到的数据总和要么为第n-2项数据的总和+n位置的数据，要么为第n-1项的数据总和。看两者哪个更大一些就取用哪个。
状态转移方程为：dp[i]=max(dp[i-1],dp[i-2]+nums[i])
💝代码实现
nums=list(map(int,input().split(','))) n=len(nums) dp=[0]*(n+10) if n==1: dp[0]=nums[0] else: dp[0]=nums[0] # 这里要注意,dp1位置的取值 dp[1]=max(nums[1],nums[0]) for i in range(2,n): dp[i]=max(dp[i-1],dp[i-2]+nums[i]) print(max(dp))
💟删除并获得点数
💝问题描述
给你一个整数数组 nums ，你可以对它进行一些操作。
每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。
之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
示例 1：
输入：nums = [3,4,2]
输出：6
解释：
删除 4 获得 4 个点数，因此 3 也被删除。
之后，删除 2 获得 2 个点数。总共获得 6 个点数。
示例 2：
输入：nums = [2,2,3,3,3,4]
输出：9
解释：
删除 3 获得 3 个点数，接着要删除两个 2 和 4 。
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
总共获得 9 个点数。
提示：
1 <= nums.length <= 2 * 104
1 <= nums[i] <= 104
💝问题分析
这个问题是大家劫舍问题的一个扩充，在这个问题中可以利用桶排序的思想将每一类数据装入字典中对应的位置
统计完次数之后，计算该类数据的数据总和，然后利用1中的思想进行求解。
其实本质没有改变。
💝代码实现
nums=list(map(int,input().split(','))) n=len(nums) t={k:0 for k in range(1,10010)} ans=[0]*10010 for i in nums: t[i]+=1 ans[1]=t[1] for i in range(2,10010): temp=t[i]*i ans[i]=max(ans[i-1],ans[i-2]+temp) print(max(ans))
💟买卖股票的最佳时机
💝问题描述
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
1 <= prices.length <= 105
0 <= prices[i] <= 104
💝问题分析
这个问题的本质其实还是一个求前缀最值的问题
对于每一个位置，股票价格已经定下来，所以我们需要找一个该位置前面最小的股票价格进行买入
由此获得最大化的利润。如果将每一个位置进行一次循环迭代，也可以得到结果，只不过数据量大的时候会很费时间。于是我们可以考虑使用动态规划进行求解。求出每一个位置的前缀最小值，然后用该位置的股票价格减去该位置的前缀最最小值即可。将最后得到的最大结果输出。
💝代码实现
prices=list(map(int,input().split(','))) n=len(prices) ans=[0]*n pmin=[0]*n pmin[0]=prices[0] for i in range(1,n): pmin[i]=min(pmin[i-1],prices[i-1]) for i in range(n): ans[i]=prices[i]-pmin[i] print(max(ans))
💟最佳观光组合
💝问题描述
给你一个正整数数组 values，其中 values[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的 距离 为 j - i。
一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，也就是景点的评分之和 减去 它们两者之间的距离。
返回一对观光景点能取得的最高分。
示例 1：
输入：values = [8,1,5,2,6]
输出：11
解释：i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11
示例 2：
输入：values = [1,2]
输出：2
提示：
2 <= values.length <= 5 * 104
1 <= values[i] <= 1000
💝问题分析
一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j可以化简为
values[i] + i + values[j] - j 对于整体得分后面的景点做出的贡献 values[j] - j 已经固定
所以只需看他前面的哪个景点 values[i] + i 最大即可。
💝代码实现
values=list(map(int,input().split(','))) n=len(values) # 构造前缀最大值数组 pmax=[0]*n pmax[0]=values[0] for i in range(1,n): pmax[i]=max(pmax[i-1],values[i-1]+i-1) # 构造景观本身评分 sel=[values[i]-i for i in range(n)] # 构造两景点最终评分 ans=[sel[i]+pmax[i] for i in range(n)] ans[0]//=2 print(max(ans))
💟最大子序和
💝问题描述
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
提示：
1 <= nums.length <= 105
-104 <= nums[i] <= 104
进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
💝问题分析
该问题有两种解法，一种是动态规划，一种是贪心策略
本题中贪心策略体现就是判断前面的所有点数之和对求解最大子序和是否有贡献
如果有的话就进行累加，如果没有的话就进行抛弃。
动态规划求解方法与贪心策略差不多
只不过动态规划把每一个位置的最大子序和都进行了保存。
💝代码实现
nums=[int(i) for i in input().split(',')] n=len(nums) maxs=nums[0] ps=nums[0] for i in range(1,n): if ps<0: ps=nums[i] else: ps+=nums[i] if ps>maxs: maxs=ps print(maxs) # 动态规划 nums=[int(i) for i in input().split(',')] n=len(nums) dp=[0]*n dp[0]=nums[0] for i in range(1,n): if dp[i-1]>0: dp[i]+=dp[i-1]+nums[i] else: dp[i]=nums[i] print(max(dp))
💟接雨水
💝问题描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，
计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
提示：
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105
💝问题分析
某位置能够容纳的最多雨水应为该位置前后最大值中的最小值减去该位置的值。
对于每个位置都是如此，所以我们可以先定义数组对某位置的前后缀最值进行保存
然后依次求解。
💝代码实现
# 柱子 height=list(map(int,input().split(','))) n=len(height) ans=0 # 前缀最大值 pmax=[0]*n pmax[0]=height[0] for i in range(1,n): pmax[i]=max(pmax[i-1],height[i-1]) # print(pmax) # 后缀最大值 nmax=[0]*n nmax[n-1]=height[n-1] for i in range(n-2,-1,-1): nmax[i]=max(nmax[i+1],height[i+1]) # print(nmax) for i in range(1,n): t=min(pmax[i],nmax[i]) if t-height[i]>0: ans+=t-height[i] print(ans)
