解题思路

这是一个经典的动态规划问题：每个订单只能选或不选，但不能选择相邻订单。 设 dp[i] 表示考虑到第 i 个订单（下标从 0 开始）时能获得的最大收入，则：

• 不选第 i 个订单：收入为 dp[i-1]
• 选第 i 个订单：由于不能选相邻，所以收入为 dp[i-2] + a[i]

状态转移：

题目内容

滴滴司机会收到预约订单，每个订单都可以选择接或不接。在每次约服务之间要有休息时间，因此他不能接受相邻的预约。给定一个预约请求序列，替滴滴司机找到最优的预约集合赚的总钱数最多，返回总的赚钱数。

输入描述

订单金额数组，$1<n<500$

输出描述

总的订单金额

样例1

输入

2 7 10 3 2

输出

14

说明

选择 $1$ 号预约、$3$ 号预约和 $5$ 号预约，总金额 $=2+10+2=14$

样例2

输入

1 2 4 1

输出

5

说明

选择 $1$ 号 $4$ 号，总金额 $=1+4=5$ 。