做网站很赚钱,深圳品牌蛋糕店有哪些品牌排行,全球设计师知识更新服务平台,织梦商城网站模板1.完全平方数
给你一个整数 n #xff0c;返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数#xff0c;其值等于另一个整数的平方#xff1b;换句话说#xff0c;其值等于一个整数自乘的积。例如#xff0c;1、4、9 和 16 都是完全平方数#xff0c;而 3 …1.完全平方数
给你一个整数 n 返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数其值等于另一个整数的平方换句话说其值等于一个整数自乘的积。例如1、4、9 和 16 都是完全平方数而 3 和 11 不是。
方法一动态规划
#方法一动态规划
def numSquares(n):dp[i for i in range(n1)] #dp[i] 表示和为i的最小完全平方数for i in range(2,n1):for j in range(1,int(i**0.5)1):dp[i]min(dp[i],dp[i-j*j]1) #状态转移方程等于前面数的最小完全平方数加上j*j这个本来就是的即1return dp[-1]
2.最长递增子序列
给你一个整数数组 nums 找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
方法一动态规划
#方法一动态规划
def lengthOfLIS(nums):dp[1 for i in range(len(nums))] #dp[i] 表示以i位置结尾的最长递增子序列res0for i in range(len(nums)):for j in range(i):if nums[j]nums[i]:dp[i]max(dp[j]1,dp[i]) #找到之前比当前位置元素小的resmax(res,dp[i])return res
3.买卖股票的最佳时机含冷冻期
给定一个整数数组prices其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下你可以尽可能地完成更多的交易多次买卖一支股票:
卖出股票后你无法在第二天买入股票 (即冷冻期为 1 天)。 注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。
方法一动态规划
#方法一动态规划
def maxProfit(prices):dp0,dp1,dp20,float(-inf),-prices[0] #dp0表示没有股票且不在冷冻期dp1表示在冷冻期dp2表示持有股票所得的利益for i in range(1,len(prices)):#dp0下一个状态 #dp1 卖出去了#dp2 要么不卖出去要么买入dp0,dp1,dp2max(dp0,dp1),dp2prices[i], max(dp0 - prices[i],dp2)return max(dp0,dp1,dp2)
