动态规划

Posted on Edited on

动态规划

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

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

  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])