动态规划(一)

我们拿到一个动态规划问题,一定要考虑三个方面:

  • 问题目标
  • 状态的定义:$opt[n]$
  • 状态转移方程:$opt[n] = \text{best_of}(opt[n-1], opt[n-2])$

下面我们举几个例子(Leetcode上的题目):

最大子序和

目标:求得数组中和最大的一个子序列

思路

  • 首先对数组进行遍历,当前最大连续子序列和为sum,结果为results
  • 如果sum > 0,则说明sum对结果有增益效果,则sum保留并加上当前遍历数字
  • 如果sum <= 0,则说明sum对结果无增益效果,需要舍弃,则sum直接更新为当前遍历数字
  • 每次比较sum 和 results的大小,将最大值置为results,遍历结束后返回结果results
  • 时间复杂度为O(n)

我们可以用数学符号表示为:

目标:

子问题:

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def maxSubArray(self, nums):
if len(nums)==1:
return nums[0]
max_ret = nums[0]
cur_max = last_max = nums[0]
for i in range(1, len(nums)):
if last_max+nums[i]<nums[i]:
cur_max = nums[i]
else:
cur_max = last_max+nums[i]
if cur_max > max_ret:
max_ret = cur_max
last_max = cur_max
return max_ret

最长上升子序列

目标是求一个数列$\{A_1,A_2,…A_n\}$中最长的子串,同时需要满足这个子串是递增的。同样我们可以定义$L(j)$为$j$位置结尾处最长的上升子序列,由此有$L(j)=max_{i<j\text{ and }A[i]<A[j]}\{L(i)\}+1$。下面我们看代码:

1
2
3
4
5
6
7
8
9
def lengthOfLIS(self, nums):
if(len(nums)<=1):
return len(nums)
mem = [1 for _ in range(len(nums))]
for j in range(1, len(nums)):
for i in range(0, j):
if nums[i] < nums[j]:
mem[j] = max(mem[j], mem[i]+1)
return max(mem)

零钱兑换

问题描述:给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。

如果这个题我们使用贪心算法有时候会失效,比如我们的目标是凑6元零钱,而有1元、3元、4元三种货币,如果用贪心算法最后组合为1个4元2个1元,共 3枚银币,而我们全局最优的解是两个3元硬币。

为了求解这个问题,我们依然设计一个数组$M[j]$来维护需要凑够$j$元的零钱所需的最小硬币数量,我们有如下递推式:

其中$v_i$为硬币种类。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def coinChange(self, coins, amount):
if amount == 0:
return 0
if len(coins) == 0:
return -1
if len(coins) == 1 and coins[0] > amount:
return -1
mem = [-1 for i in range(amount+1)]
mem[0] = 0
for i in range(1, amount + 1):
cur_min = amount + 1
for c in coins:
if c <= i:
cur_min = mem[i-c] if mem[i-c] < cur_min else cur_min
mem[i] = cur_min + 1 if cur_min<amount+1 else amount+1
if mem[-1] == amount + 1:
return -1
else:
return mem[-1]

0-1背包问题

你只有一个容量有限的背包,总容量为c,有n个可待选择的物品,每个物品只有一件,它们都有各自的重量和价值,你需要从中选择合适的组合来使得你背包中的物品总价值最大。例如下图的对应关系:

我们定义$M[i,j]$为可选物品为前$i$件时且背包容量为$j$时的物品最大价值。由此我们可以导出状态转移方程:

1
2
3
4
5
6
7
8
9
def knapsack(w, v, c):
mem = np.zeros((len(w)+1, c+1))
for i in range(1, len(w)+1):
for j in range(1, c+1):
if w[i-1]<=j:
mem[i,j] = max(mem[i, j], mem[i-1,j], mem[i-1,j-w[i-1]]+v[i-1])
else:
mem[i,j] = mem[i-1,j]
return mem
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!

扫一扫,分享到微信

微信分享二维码
  • Copyrights © 2020 chenk
  • 由 帅气的CK本尊 强力驱动
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信