动态规划相关题目都可以参考以下五个步骤进行解答：
状态表?
状态转移?程
初始化
填表顺序
返回值
后面题的解答思路也将按照这五个步骤进行讲解。
一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
注意：本题相对原题稍作改动
class Solution {
public int massage(int[] nums) {
}
}
对于简单的线性 dp ，我们可以?「经验+题?要求」来定义状态表?：
这?我们选择?较常?的?式，以某个位置为结尾，结合题?要求，定义?个状态表?：
dp[i] 表?：选择到 i 位置时，此时的最?预约时?。
但是我们这个题在 i 位置的时候，会?临「选择」或者「不选择」两种抉择，所依赖的状态需要细分：
因为状态表?定义了两个，因此我们的状态转移?程也要分析两个：
对于 f[i] ：
对于 g[i] ：
初始化：
这道题的初始化?较简单，因此?需加辅助节点，仅需初始化 f[0] = nums[0], g[0] = 0 即可。
填表顺序
根据「状态转移?程」得「从左往右，两个表?起填」。
返回值
根据「状态表?」，应该返回 max(f[n - 1], g[n - 1]) 。
class Solution
{
public int massage(int[] nums)
{
// 1. 创建 dp 表
// 2. 初始化
// 3. 填表
// 4. 返回值
int n = nums.length;
if(n == 0) return 0; // 处理边界条件
int[] f = new int[n];
int[] g = new int[n];
f[0] = nums[0];
for(int i = 1; i < n; i++)
{
f[i] = g[i - 1] + nums[i];
g[i] = Math.max(f[i - 1], g[i - 1]);
}
return Math.max(g[n - 1], f[n - 1]);
}
}
当然博主这里还提供另一种解题方法，就不讲解了，直接给出代码，代码如下：
class Solution {
public int massage(int[] nums) {
int len = nums.length;
if(len == 0) {
return 0;
}
if(len == 1) {
return nums[0];
}
int[] dp = new int[len + 1];
dp[1] = nums[0];
dp[2] = nums[1];
for(int i = 3; i <= len ; i++) {
int max = Math.max(dp[i-2],dp[i-3]);
dp[i] = nums[i-1] + max;
}
return Math.max(dp[len-1],dp[len]);
}
}
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
这?个问题是「打家劫舍I」问题的变形。
上?个问题是?个「单排」的模式，这?个问题是?个「环形」的模式，也就是?尾是相连的。但是我们可以将「环形」问题转化为「两个单排」问题：
两种情况下的「最?值」，就是最终的结果。
因此，问题就转化成求「两次单排结果的最?值」。
class Solution
{
public int rob(int[] nums) {
int n = nums.length;
return Math.max(nums[0] + rob1(nums, 2, n - 2), rob1(nums, 1, n - 1));
}
public int rob1(int[] nums, int left, int right) {
if(left > right) return 0;
// 1. 创建 dp 表
// 2. 初始化
// 3. 填表
// 4. 返回
int n = nums.length;
int[] f= new int[n];
int[] g= new int[n];
f[left] = nums[left];
for(int i = left + 1; i <= right; i++)
{
f[i] = g[i - 1] + nums[i];
g[i] = Math.max(g[i - 1], f[i - 1]);
}
return Math.max(f[right], g[right]);
}
}
给你一个整数数组 nums ，你可以对它进行一些操作。
每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
class Solution {
public int deleteAndEarn(int[] nums) {
}
}
其实这道题依旧是「打家劫舍I」问题的变型。
我们注意到题?描述，选择 x 数字的时候， x - 1 与 x + 1 是不能被选择的。像不像「打家劫舍」问题中，选择 i 位置的?额之后，就不能选择 i - 1 位置以及 i + 1 位置的?额呢~
因此，我们可以创建?个??为 10001 （根据题?的数据范围）的 hash 数组，将nums 数
组中每?个元素 x ，累加到 hash 数组下标 x 的位置处，然后在 hash 数组上来?次「打家劫舍」即可
class Solution {
public int deleteAndEarn(int[] nums) {
int[] arr = new int[10001];
for(int i = 0; i < nums.length; i++) {
arr[nums[i]] += nums[i];
}
int[] f= new int[10001];
int[] g= new int[10001];
f[0] = arr[0];
for(int i = 1; i < 10001; i++)
{
f[i] = g[i - 1] + arr[i];
g[i] = Math.max(g[i - 1], f[i - 1]);
}
return Math.max(f[10000], g[10000]);
}
}
关于《【算法优选】 动态规划之简单多状态dp问题——壹》就讲解到这儿，感谢大家的支持，欢迎各位留言交流以及批评指正，如果文章对您有帮助或者觉得作者写的还不错可以点一下关注，点赞，收藏支持一下！