动态规划的三要素:最优子结构,边界和状态转移函数,最优子结构是指每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到(子问题的最优解能够决定这个问题的最优解),边界指的是问题最小子集的解(初始范围),状态转移函数是指从一个阶段向另一个阶段过度的具体形式,描述的是两个相邻子问题之间的关系(递推式)
重叠子问题,对每个子问题只计算一次,然后将其计算的结果保存到一个表格中,每一次需要上一个子问题解时,进行调用,只要o(1)时间复杂度,准确的说,动态规划是利用空间去换取时间的算法.
判断是否可以利用动态规划求解,第一个是判断是否存在重叠子问题,
例子:
爬楼梯 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 注意：给定 n 是一个正整数。 示例 1： 输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶 示例 2： 输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶
https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/23/dynamic-programming/54/
分析: 假定n=10,首先考虑最后一步的情况,要么从第九级台阶再走一级到第十级,要么从第八级台阶走两级到第十级,因而,要想到达第十级台阶,最后一步一定是从第八级或者第九级台阶开始.也就是说已知从地面到第八级台阶一共有X种走法,从地面到第九级台阶一共有Y种走法,那么从地面到第十级台阶一共有X+Y种走法.
即F(10)=F(9)+F(8) 分析到这里,动态规划的三要素出来了. 边界:F(1)=1,F(2)=2 最优子结构:F(10)的最优子结构即F(9)和F(8) 状态转移函数:F(n)=F(n-1)+F(n-2)
求解: class Solution(object): def climbStairs(self, n): """ :type n: int :rtype: int """ if n<=2: return n a=1 #边界 b=2 #边界 temp=0 for i in range(3,n+1): temp=a+b #状态转移 a=b #最优子结构 b=temp #最优子结构 return temp
矿工挖矿问题:
某一个地区发现了5座金矿,每个金矿的黄金储量不同,需要挖掘的工人也不同,设参加挖掘的总共10人,且每座金矿要么全挖,要么不挖,不能派出一半人挖取一般金矿
金矿 黄金储量 工人数
1 400 5
2 500 5
3 200 3
4 300 4
5 350 3
分析: 如果要使用动态规划解决,必须要满足三个条件; 首先确定最优子结构,解题目标是确定10个工人挖5座金矿时能够获得最多的黄金数量,该结果可以从10个工人挖4座金矿的子问题递归求解. 10个人挖掘4个金矿的过程中,存在两种选择,一种是放弃第5座金矿,把10全放入4座金矿的挖掘中,另一种是挖掘第5座金矿,那么10人中的3人取挖掘5座金矿,因此,最优解为上面两种方案的其中一个. 为了描述方便,假设金矿的数量为n(1-n),工人的数量为w,当前获得的黄金数量为G[n],当前所用的矿工数量为P[n],根据上述分析买药获得10个矿工挖掘第5座金矿的最优解F(5,10),需要在F(4,10),和F(4,10-P[5])+G[4] 中获得最大值.即 F(5,10)=max(F(4,10),F(4,10-P[5])+G[5])
之后,我们考虑问题的边界,对于第一座金矿来说,当前矿工人数不满足金矿所需人数,则其获得黄金为0,满足要求则为G[1],因此该边界问题为(索引从0开始):
当n=1,w>=P[0]时,F(n,w)=G[0]
当n=1,w<P[0]时,F(n,w)=0
综上,可以得到该问题的状态转移函数:
F(n,w)=0(n<=1,w<p[0])
F(n,w)=0(n==1,w>=p[0])
F(n,w)=F(n-1,w)(n>1,w<p[n-1])
F(n,w)=max(F(n-1,w),F(n-1,w-P[n-1])+G[n-1])(n>1,w>p[n-1])
53. 最大子序和 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 https://leetcode-cn.com/problems/maximum-subarray/
#分析: 利用动态规划的思路解题: 首先寻找最优子问题,[-2,1,-3,4,-1,2,1,-5,4],第一个最优子问题为-2,那么到下一个1时,其最优为当前值或者当前值加上上一个最优值,因而可以得到其递推公式
状态转移方程
dp[i] = max(nums[i], nums[i] + dp[i - 1])
解释
- i代表数组中的第i个元素的位置
- dp[i]代表从0到i闭区间内，所有包含第i个元素的连续子数组中，总和最大的值
nums = [-2,1,-3,4,-1,2,1,-5,4]
dp = [-2, 1, -2, 4, 3, 5, 6, 1, 5]
class Solution(object): def maxSubArray(self, nums): """ :type nums: List[int] :rtype: int """ # 判断边界
if len(nums)==0: return 0 # 定义一个表格进行存储上一个子问题的最优解 d=[] d.append(nums[0]) #第一个最优解为第一个元素 max_=nums[0] #返回的最大值 for i in range(1,len(nums)): if nums[i]>nums[i]+d[i-1]: d.append(nums[i]) else: d.append(nums[i]+d[i-1]) if max_<d[i]: max_=d[i] return max_
198. 打家劫舍 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。 示例 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 。 https://leetcode-cn.com/problems/house-robber/
class Solution(object): def rob(self, nums): """ :type nums: List[int] :rtype: int """ # 思路:由该例子解析:[1,2,3,1],最后一个1,该点有两种操作,一个是偷取,那么的加上在2处的最优解,不偷取,获取3处的最优解.因而f(1)的最优子解为max(f(2)+1,f(3))转移方程:d[i]=max(d[i-1],d[i-2]+nums[i]) , 边界 d[0]=nums[0],d[1]=max(nums[0],nums[1]) if len(nums)==0: return 0 if len(nums)<=2: return max(nums) dp=[] dp.append(nums[0]) dp.append(max(nums[0],nums[1])) for i in range(2,len(nums)): dp.append(max(dp[i-1],dp[i-2]+nums[i])) return dp[-1]
121. 买卖股票的最佳时机 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。 注意你不能在买入股票前卖出股票。 示例 1: 输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。 示例 2: 输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。 https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
class Solution(object): def maxProfit(self, prices): """ :type prices: List[int] :rtype: int """ # 思路：动态规划，设置一个变量记录买入的最小金额 # [7,1,5,3,6,4] 从最后一个4开始分析，比如我从4卖出，那么其获得的最大利润为（6）的时候最大利润与（4）-最小值之间的最大值， # 递推式为 f（4）=max（f（6），4-最小金额） 边界： f（0）=0，最优子结构：f（4）的最有子结构为f（6） if len(prices)<=1: return 0 dp=[] dp.append(0) min_value=prices[0] for i in range(1,len(prices)): dp.append(max(dp[i-1],prices[i]-min_value)) if prices[i]<min_value: min_value=prices[i] return dp[-1]
746. 使用最小花费爬楼梯 数组的每个索引做为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 cost[i](索引从0开始)。 每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。 您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。 示例 1: 输入: cost = [10, 15, 20] 输出: 15 解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。 示例 2: 输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 输出: 6 解释: 最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。 注意： cost 的长度将会在 [2, 1000]。 每一个 cost[i] 将会是一个Integer类型，范围为 [0, 999] https://leetcode-cn.com/problems/min-cost-climbing-stairs/
class Solution(object): def minCostClimbingStairs(self, cost): """ :type cost: List[int] :rtype: int """ # 思路： 从楼顶分析，比如说10为楼顶，到达楼顶只有两种方式，一种从第八层走两步到达，一种是从第九层走一步到达，因为该10为楼顶其： # 10为楼顶：F(10)最有子结构为: F(9) 和 F(8) # F（10） 递推式： F(10)=min(F(9)+cost[9],F(8)+cost[8]) # 边界: F(0)=1 F(1)=100 # if len(cost)<=1: return min(cost) dp=[] dp.append(cost[0]) dp.append(cost[1]) for i in range(2,len(cost)+1): #楼顶不在cost的范围内，因为对遍历+1 if i==len(cost): #该层为楼顶，没有取值 dp.append(min(dp[i-1],dp[i-2])) else: dp.append(min(dp[i-1]+cost[i],dp[i-2]+cost[i])) return dp[-1]
338. 比特位计数 给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。 示例 1: 输入: 2 输出: [0,1,1] 示例 2: 输入: 5 输出: [0,1,1,2,1,2] 进阶: 给出时间复杂度为O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)内用一趟扫描做到吗？ 要求算法的空间复杂度为O(n)。 你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount）来执行此操作。
class Solution(object): def countBits(self, num): """ :type num: int :rtype: List[int] """ # 动态规划问题：当数字i未2的指数倍时，其只有一个1，dp[i]=1 if(i==2**k) # 递推试 ： dp[i] = 1+dp[i-2**k] res=[0] k=0 for i in range(1,num+1): if(i == 2**k): res.append(1) k+=1 else: res.append(1+res[i-2**k]) return res
120. 三角形最小路径和 给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。 例如，给定三角形： [ [2], [3,4], [6,5,7], [4,1,8,3] ] 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。 说明： 如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。
class Solution(object): def minimumTotal(self, triangle): """ :type triangle: List[List[int]] :rtype: int """ ''' dp问题：利用列表进行存储，每一行每个步骤结束后的最小值，那么在最后一行，其最小值为min（4+dp[0],4+dp[1],1+dp[0],1+dp[1]...） 所以状态转移方程为： 如果i==0 or i==len(triangle[row]) 那么其转移方程为dp[i]=dp[0]triangle[row][i] dp[i]=dp[i-1]+triangle[row][i] dp[i]=min(dp[i-1],dp[i])+triangle[row][i] 初始值为 dp[0]=triangle[0][0] ''' if len(triangle)==1: return triangle[0][0] dp=[[triangle[0][0]]] for i in range(1,len(triangle)): for j in range(len(triangle[i])): dp.append([]) # 边界只有一个邻边 if j==0: dp[i].append(dp[i-1][j]+triangle[i][j]) elif j==len(triangle[i])-1: dp[i].append(dp[i-1][j-1]+triangle[i][j]) else: # 当前取值，在上一层的邻边最小值相加 dp[i].append(min(dp[i-1][j-1],dp[i-1][j])+triangle[i][j]) return min(dp[len(triangle)-1])