动态规划
动态规划
动态规划,无非就是利用历史记录,来避免我们的重复计算。而这些历史记录,我们得需要一些变量来保存,一般是用一维数组或者二维数组来保存。
动态规划题很重要的三个步骤
定义数组元素的含义
假设用一维数组 dp[] 表示历史记录,这个时候我们需要定义dp[i] 是代表什么意思
找出数组元素之间的关系式
当我们要计算 dp[n] 时,是可以利用 dp[n-1],dp[n-2]…..dp[1],来推出 dp[n] 的,也就是可以利用历史数据来推出新的元素值,所以我们要找出数组元素之间的关系式,例如 dp[n] = dp[n-1] + dp[n-2],这个就是他们的关系式。
找出初始值
leetcode 按摩师
一个有名的按摩师会收到源源不断的预约请求,每个预约都可以选择接或不接。
在每次预约服务之间要有休息时间,因此她不能接受相邻的预约。
给定一个预约请求序列,替按摩师找到最优的预约集合(总预约时间最长),返回总的分钟数。
解法
- 定义数组元素含义
- dp[i][0]表示前i个预约中第i个预约不接的总时长
- dp[i][1]表示前i个预约中第i个预约接的总时长
- 找出数组元素之间的关系式(转移方程)
- 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])
- 找出初始值
- 没有预约的时候总时长为0,dp[i][0] = 0, dp[i][1] = 0;
python代码
1 | class Solution(object): |