这两天学习动态规划的总结，如果有错误请指出
动态规划
[TOC]
四个步骤
1. 设计暴力解法，找到冗余
暴力的关键在于如何找到最优子结构、子结构没有后效性（即N可有N-1得出，N-1和N的状态无关）
2. 设计并储存状态（一维、二维数组）
根据子问题得到状态
3. 递归式（状态转移方程）
4. 自底向上求解最优解
(上面这个来自七月算法上面动态规划的课程，不过我还是一直没理解第四部的含义，所以我自己的第4步，通常是找边界条件)
最长递增子序列
leetcode 300.
解题思路
- 数组A存放各个元素，要想得到结尾是A[i]的最长子序列，我们需要得到以在A[:i]中，小于A[i]的数结尾的最长子序列。我们将以第i位元素结尾的最长子序列记做mem[i]。
- 可以容易得到，mem[0]=1。
- 之后对i>=1,我们要找到A[:i]中小于A[i]的数的索引indexs = [j for j in range(i) if arr[i]>arr[j]]
- 然后找到mem[indexs]中最大数，加1即为mem[i]的值mem[i]=max([mem[x] for x in indexs])+1
- 这里要注意，如果indexs==[]，则直接让mem[i]=1
- 最后max(mem)即为所求
代码
# -*-coding:utf8-*-
class Solution():
def lengthOfLIS(self, arr):
if len(arr) == 0:
return 0
mem = [0] * len(arr)
for i in range(len(arr)):
if i == 0:
mem[i] = 1
else:
# 找到小于arr[i]的索引
indexs = [j for j in range(i) if arr[i] > arr[j]]
if len(indexs) > 0:
# 满足小于arr[i]的索引的mem值的最大值
mem[i] = max([mem[x] for x in indexs]) + 1
else:
mem[i] = 1
return max(mem)
==
==
s = Solution()
print s.lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])
房屋抢劫
leetcode 198. House Robber
解题思路
- "最多抢多少钱啊"，最大化题设，是个动态规划题目。
- 一共有len(nums)个房子，问抢到最后一个房子nums[-1]能抢多少钱
- 定义函数sob(idx,num)是抢到第idx有的钱
- 到idx能抢到的钱有两种可能：
- 抢了idx,说明idx-1是不能抢的，现在手里的钱应该是sob(idx-2,nums)+nums[idx]
- 没有抢idx,说明抢了idx-1，现在手里的钱是sob(idx-1,nums)
- 所以现在能有的钱最多的就是max(sob(idx-2,nums)+nums[idx],sob(idx-1,nums))
- 先看终止条件，如果idx==0,最多抢nums[idx],如果idx==1,最多抢max(nums[0],nums[1])
- 为了计算方便，我们将中间结果保存在数组dp里,给定初值dp[0]=nums[0],dp[1]=max(nums[0],nums[1]),其他为-1
代码
class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums)==0:
return 0
if len(nums)==1:
return nums[0]
if len(nums)==2:
return max(nums[0],nums[1])
dp = [-1]*len(nums)
dp[0] = nums[0]
dp[1] = max(nums[:2])
return self.robmax(nums,len(nums)-1,dp)
def robmax(self,nums,idx,dp):
if dp[idx]!=-1:
return dp[idx]
else:
dp[idx]=max(self.robmax(nums,idx-1,dp),
self.robmax(nums,idx-2,dp)+nums[idx])
return dp[idx]
subsetsum问题
题目
给定数组a(都是正数),目标和S,给出和为S的a的子数组的最小长度，如果无法得到返回-1。
解题思路
- 定义状态v(i,j)考虑第i个数，和为j,最少的数字数目。
- 两种子状态：
- 用了第i个数 v(i-1,j-a[i])+1
- 没用 v(i-1,j)
- v(i,j)=min(两种子状态)
- 终止条件：
- 首先考虑初始条件即i=0时刻（先考虑i的原因是不对i<0做处理，而且更好理解），如果i==0时，a[i]=j,则return 1；否则return inf。可以这里理解，在只有一个数的时候，如果还不等于j，那之后没有可以继续递归的了，这就是终止条件。
- 其他的都是中间的终止条件，如果j<0,则返回inf，如果j=0，则返回0。试想，如果你再考虑第i个数要求和为0，则不管之前的结果，这一状态的值一定是0;j<0同理，考虑第i个数要求j<0,则无论如何不能实现。
- (不用考虑a[i]是不是小于j,因为我们是在考虑第i个数的时候，即便a[i]>j，只是在求他的子状态时，没用这个数而已)
代码
# -*-coding:utf8-*-
def coinChange(coins, W):
n = len(coins)
dp = []
for i in range(n):
dp.append([float('inf')] * (W + 1))
# dp[idx][W] 存放的是考虑idx时,和为W最小硬币数目
res = minCount(n - 1, W, coins, dp)
if res == float('inf'):
return -1
else:
return res
def minCount(idx, W, coins, dp):
if W == 0:
return 0
if W < 0:
return float('inf')
if idx < 0:
return float('inf')
if dp[idx][W] != float('inf'):
return dp[idx][W]
a = minCount(idx - 1, W - coins[idx], coins, dp) + 1
b = minCount(idx - 1, W, coins, dp)
dp[idx][W] = min(a, b)
return dp[idx][W]
print coinChange([2, 4, 3, 6], 16)
0-1背包问题
题目
有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？
解题思路
- 根据子问题得到状态 我们的问题是将5个物品，放进承重是10的背包的最大值，子问题是将四个物品，放进承重为x背包的价值最大值，所以我们的状态就是v(i,j)，将第i个物品，放进容量为j的背包的价值最大值。
- v(i,j)对于物品i来讲，有两种子状态
- 放进去 v(i-1,j-w[i])+v[i],
- 不放进去 v(i-1,j)
- v(i,j)=max(两种状态)
- 考虑终止条件：
- 先考虑i=0时刻，这时如果w[i]>j，return -inf（不写0的原因是因为避免0+v[i]，我们的目的是说明这种情况最终不会有价值），如果w[i]<=j，返回v[i]
- 中间的终止条件，如果j<0,则返回-inf；如果j=0,则返回0
代码
# -*-coding:utf8-*-
def bag0_1(weights, values, W):
n = len(weights)
dp = []
for i in range(n):
dp.append([-float('inf')] * (W + 1))
# dp[idx][W] 考虑idx时,
res = maxVal(n - 1, W, weights, values, dp)
return 0 if res == -float('inf') else res
def maxVal(idx, W, weights, values, dp):
if idx==0:
if weights[idx]<=W:
return values[idx]
else:
return -float('inf')
if W == 0:
return 0
if W < 0:
return -float('inf')
if dp[idx][W] != -float('inf'):
return dp[idx][W]
dp[idx][W] = max(maxVal(idx - 1, W - weights[idx], weights, values, dp) + values[idx],
maxVal(idx - 1, W, weights, values, dp))
return dp[idx][W]
print bag0_1([2,2,6,5,4], [6,3,5,4,6], 10)