【leecode刷题】初级算法-动态规划

1、爬楼梯

（1）传统解法

def climbStairs(n): f1, f2 = 1, 2 while n > 1: f1, f2 = f2, f1 + f2 n -= 1 return f1

（2）递归解法

def climbStairs(n): if n==1: return 1 elif n==2: return 2 else: return climbStairs(n-1)+climbStairs(n-2)

（3）带记忆性的递归解法

def climbStairs(n,L): if n==1: L[n] =1 return 1 elif n==2: L[n] =2 return 2 elif L[n]>0: return L[n] else: L[n] = climbStairs(n-1,L)+climbStairs(n-2,L) return climbStairs(n-1,L)+climbStairs(n-2,L)

（4）动态规划解法

def climbStairs(n,L): for i in range(1,n+1): if i==1: L[i] = 1 elif i==2: L[i] = 2 else: L[i] = L[i-1]+L[i-2] return L[n]

2、买卖股票的最佳时机

（1）循环解法

def maxProfit(prices): result = 0 for i in range(len(prices)): for j in range(i+1,len(prices)): if prices[j]>prices[i]: result = max(result,prices[j]-prices[i]) return result

（2）动态规划算法

def maxProfit(prices): inf = int(1e9) minprice = inf maxprofit = 0 for price in prices: maxprofit = max(price - minprice, maxprofit) minprice = min(price, minprice) return maxprofit

3、最大子序和

（1）循环解法

def maxSubArray(nums): if len(nums)==1: return nums[0] else: maxValue = nums[0] for index in range(len(nums)): for length in range(1,len(nums)-index+1): # print(index,length,sum(nums[index:index+length])) maxValue = max(maxValue,sum(nums[index:index+length])) return maxValue

（2）动态规划解法

def maxSubArray(nums): dp=[0]*(len(nums)) dp[0]=nums[0] for i in range(1,len(nums)): if dp[i-1]<=0: dp[i]=nums[i] else: dp[i]=dp[i-1]+nums[i] return max(dp)

4、打家劫舍

（1）动态规划算法

def rob(nums): if not nums: return 0 size = len(nums) if size == 1: return nums[0] dp = [0] * size dp[0] = nums[0] dp[1] = max(nums[0], nums[1]) for i in range(2, size): dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]) return dp[size - 1]

（2）动态规划算法+滚动数组

def rob(nums): if not nums: return 0 size = len(nums) if size == 1: return nums[0] firstValue = nums[0] secondValue = max(nums[0], nums[1]) for i in range(2, size): firstValue,secondValue = secondValue,max(firstValue + nums[i], secondValue) return secondValue