动态规划

动态规划

动态规划,无非就是利用历史记录,来避免我们的重复计算。而这些历史记录,我们得需要一些变量来保存,一般是用一维数组或者二维数组来保存。

动态规划题很重要的三个步骤

  1. 定义数组元素的含义

    假设用一维数组 dp[] 表示历史记录,这个时候我们需要定义dp[i] 是代表什么意思

  2. 找出数组元素之间的关系式

    当我们要计算 dp[n] 时,是可以利用 dp[n-1],dp[n-2]…..dp[1],来推出 dp[n] 的,也就是可以利用历史数据来推出新的元素值,所以我们要找出数组元素之间的关系式,例如 dp[n] = dp[n-1] + dp[n-2],这个就是他们的关系式。

  3. 找出初始值

leetcode 按摩师

一个有名的按摩师会收到源源不断的预约请求,每个预约都可以选择接或不接。
在每次预约服务之间要有休息时间,因此她不能接受相邻的预约。
给定一个预约请求序列,替按摩师找到最优的预约集合(总预约时间最长),返回总的分钟数。

来源:力扣(LeetCode)

解法

  1. 定义数组元素含义
    • dp[i][0]表示前i个预约中第i个预约不接的总时长
    • dp[i][1]表示前i个预约中第i个预约接的总时长
  2. 找出数组元素之间的关系式(转移方程)
    • i-1 可接可不接 dp[i][0] = max(dp[i-1][0],dp[i-1][1])
    • i-1 不可接相邻的 加上这次的预约时间 dp[i][1] = dp[i-1][0] + nums[i]
    • 故 第i次预约时间最长的是接与不接较大的那一个: dp[i] = max(dp[i][0], dp[i][1])
  3. 找出初始值
    • 没有预约的时候总时长为0,dp[i][0] = 0, dp[i][1] = 0;

python代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def massage(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
if n == 0:
return 0
dp = [
[0], # 不接受
[nums[0]] # 接受
]
for i in range(1, n):
dp[0].append(max(dp[0][i-1], dp[1][i-1]))
dp[1].append(dp[0][i-1] + nums[i])
return max(dp[0][n-1], dp[1][n-1])