本文共 2877 字，大约阅读时间需要 9 分钟。
笔试刷题必备------ 动态规划
笔试刷题必备------ 动态规划
爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2输出： 2
解释： 有两种方法可以爬到楼顶。
-
1 阶 + 1 阶
-
2 阶
示例 2：输入： 3
输出： 3 解释： 有三种方法可以爬到楼顶。 -
1 阶 + 1 阶 + 1 阶
-
1 阶 + 2 阶
-
2 阶 + 1 阶
class Solution(object): def climb_stairs(self,n): if n <= 0: return None dp = [-1]*(n+1) dp[0] = 1 dp[1] = 1 for i in range(2,n+1): dp[i] = dp[i-1]+dp[i-2] return dp[n]if __name__ == "__main__": solu = Solution() print(solu.climb_stairs(3))
买卖股票的最佳时机
给定一个数组，它的第 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
class Solution(object): def max_profit(self,prices): min_buy_prices = prices[0] dp = [0] profit = 0 for i in range(1,len(prices)): min_buy_prices = min(min_buy_prices,prices[i]) dp.append(max(dp[i-1],prices[i]-min_buy_prices)) if dp[-1] > profit: profit = dp[-1] return profit
打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 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 。class Solution(object): def rob(self,nums): last = 0 now = 0 for i in nums: last,now = now,max(last+i,now) return now
最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
动态规划
class Solution(object): def max_sub_array(self,nums): for i in range(1,len(nums)): nums[i] = max(nums[i-1]+nums[i],nums[i]) return max(nums)
Longest Increasing Subsequence
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:
可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。 进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?解题思路：
使用动归。用Dp[i]来保存从0-i的数组的最长递增子序列的长度。如上数组Dp[0]=1,Dp[1]=1,Dp[2]=1,Dp[3]=2,Dp[4]=2。。。计算Dp[i]的值可以对Dp[i]之前数值进行遍历，如果nums[i]>nums[j],则Dp[i] = max(Dp[i],Dp[j]+1)。复杂度为O(n*n)
class Solution(object): def length_of_LIS(self,nums): if nums == []: return 0 dp = [1]*len(nums) for i in range(len(nums)-1): for j in range(i+1): if nums[i+1] > nums[j]: dp[i+1] = max(dp[i+1],dp[j]+1) return max(dp)
不同路径
输入: m = 3, n = 2输出: 3解释:从左上角开始，总共有 3 条路径可以到达右下角。1. 向右 -> 向右 -> 向下2. 向右 -> 向下 -> 向右3. 向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3输出: 28
class Solution(object): def unique_paths(self,m,n): if m <= 0 or n <= 0: return 0 dp = [[-1]*n]*m for i in range(m): dp[i][0] = 1 for j in range(n): dp[0][j] = 1 for i in range(1,m): for j in range(1,n): dp[i][j] = dp[i-1][j]+dp[i][j-1] return dp[m-1][n-1]
转载地址：http://lluib.baihongyu.com/