动态规划的经典例题

Posted on

偷珠宝问题

一条直线上，有 n 个房间，每个房间数量不等的财宝，一个盗贼希望从房屋中盗取财宝，由于房屋有警报器，同时从相邻两个房间盗取珠宝就会触发警报，若不触发警报，最多可获取多少财宝？

解决思路

从动态规划的角度考虑，假设小偷站在第 i 个 房间的门前，这个时候他偷不偷是受前面状态影响的。如果第 i-1 个房间可以获得的最大金钱比第 i-2 个加上第 i 个要多的话，那么就应该选择偷取第 i-2 个房间和第 i 个房间，反之则偷取第 i-1 个房间，而放弃第 i 个房间。
状态转移公式：

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import random
def stealMoney(n):
	"""
	输入房子有 n 座，随机生成金额
	"""
    value = np.random.randint(20,size=n)
    dp = np.zeros(value.shape)
    print(value)
    for i in range(n):
        if i <= 1 : 
            dp[i] = value[i]
        else:
            dp[i] = max( dp[i-2] + value[i] , dp[i-1] )
    print(dp)
    return dp[-1]

假设房间是围成一个圆圈呢？思考了一下，给一个大概的思路：

任意选择一点，切分圆成为一条线段，按照上文的思路去计算前三个点，那么

  • 如果取第一个点，则对[2,-2]进行dp，最后加上第一个点的值
  • 如果取第二个点，则对[1,-1]进行dp

最大子序列和问题

给定一个数组（考虑正负），求这个数组的连续子数组中，最大的那一段的和。

解决思路

假设我们考虑第 i 个数，这个时候我们有记录了前面最大子数组的 dp[i-1],那我们只需要取 dp[i-1] + value[i] 和 value[i] 的最大值即可。
状态迭代公式：

算法实现

1
2
3
4
5
6
def getArrMaxSubSum(arr):
    dp = [0 for i in range(len(arr))]
    dp[0] = arr[0]
    for k in range(1,len(arr)):
        dp[k] = max(dp[k-1]+arr[k],arr[k])
    return dp[-1]

找零钱问题

已知不同面值的钞票，求如何用最少数量的钞票组成某个金额，求可以使用的最少钞票数量。如果任意数量的已知面值钞票都无法组成该金额，则返回 -1 。

解决思路

给定一个 account 和一个 coins[1,2,5,10] 数组。我们从头开始看：

  • 如果金额是 1 元，则肯定是 1 张，即dp[1] = 1
  • 如果是 2 元的话，那么其实有两种选择，1 + 1 或者 2 , 有两种选择
  • 如果是 8 元的话，那么
    • 8 = dp[7] + 1 , 1 元配上 7 元的最优解
    • 8 = dp[6] + 1 , 2 元配上 6 元的最优解
    • …

也就是需要遍历一下，才可以得到最优解。即归纳出 dp[i] = min(dp[i],dp[i-coins[j]] + 1 )

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
def checkCoins(money):
	coins = [1,5,11] # 初始化硬币
	dp = [money + 1  for i in range(money+1)] #初始化 dp 数组
	dp[0] = 0
	for i in range(1,money+1):
		for j in range(len(coins)):
			if coins[j] <= i: # 硬币如果比钱小，则计算，如果一个硬币刚好够，则只需要一次, dp[0] = 0
				dp[i] = min(dp[i],dp[i-coins[j]]+1) # 两次遍历得到最优结果
	if dp[money] > money:
		return -1 
	else:
		return dp[money]