解锁动态规划的奥秘：从零到精通的创新思维解析（7）
解锁动态规划的奥秘：从零到精通的创新思维解析（7）
前言：
在前几天的文章中，小编为大家讲解了动态规划中多状态 DP 问题的相关内容。今天，我们将延续上篇文章的主题，继续深入剖析多状态 DP 的解题思路和技巧。快系好安全带，准备好，我们的算法世界之旅再次启程！
正文：
1.打家劫舍
1.1.题目来源
与之前的题目一样，本题同样来自于力扣，下面小编给出本题的链接：LCR 089. 打家劫舍 - 力扣（LeetCode）
1.2.题目分析
本题分析起来也是比较容易的，此时有一个小偷，它准备偷沿街的房屋，每个房子都有钱，此时小偷可以选择偷当前房子的金钱或者不选择偷取，并且此时相邻房子因为有防盗系统，所以我们偷取一个房子的前钱后，此时下一个房子指定是不可以偷取了，此时我们可以根据这个特性来书写状态转换方程，之后让我们寻找一个方案，使得我们可以偷得最高的金额，此时这就是本题目的分析环节，下面我们就进入题目的思路讲解环节。
1.3.题目思路讲解
此时对于动态规划的题目，我们同样是划分为五步走，对于dp表的建立，此时我们根据题目分析，可以知晓我们需要两个表来解决本题，分别是f表和g表，下面我们就进入本题目的五步走环节。
1.状态表示
通过题目的分析，我们可以让f[i]表示到达i位置的时候，偷取该位置的金额；g[i]表示到达i位置的时候，不偷取该位置的金额 ；通过此时的状态表示，就可以表示出状态转换方程了。
2.状态转换方程
对于状态转移方程，此时我们也是需要分为两部分完成的，一部分是f[i]的书写，另一部分是g[i]的书写。此时我们先分析f[i]的状态转换方程的书写。
我们在状态表示的阶段就知道了f[i]代表着到达i位置时，偷走该房子的金钱，所以我们根据它前一个位置就可以判断出此时的f[i]的状态转换方程，因为相邻位置的金钱不可以被偷取，所以此时我们可以知道它的前一个位置只可以是g[i - 1]，此时我们在加上当前位置的金额就可以得出状态转换方程。
f[i] = g[i - 1] + 1;
之后我们在分析g[i]的状态转换方程，此时我们依旧是分析前一个位置的方程，只不过此时我们要分为两种情况进行讨论，一种是在i-1的时候并没有选择偷取，那么就是g[i - 1]；另一种是在i-1位置的时候选择偷取钱财，那么就是f[i - 1]，我们需要选取其中最大的作为g[i]，所以此时我们就可以很快得出状态方程。
g[i] = max(g[i - 1],f[i - 1]);
3.初始化
此时我们写完状态转换方程后，就需要考虑一些细节问题了，其中最主要的就是初始化的问题，因为此时我们需要根据前一个位置来确定当前的位置，当我们在第一个位置的时候，前一个位置是没有的，所以我们需要对第一个位置进行初始化，初始化的时候我们需要依靠状态表示来定义，因此此时的f[0]代表在第0个位置的时候选择偷取金额，所以此时f[0]就是表示nums[0]，而g[0]表示第0个位置的时候不选择偷取，所以此时我们初始化为0即可，此时我们的初始化工作就完成了。
4.填表顺序
因为此时我们需要前一个位置的数据，所以应该是从左到右。
5.返回值
此时我们需要返回最后一个位置的元素，因为此时涉及到两个表，所以我们需要返回它们两个中的最大值即可。
此时我们已经讲完了理论部分，下面进入代码实操教学。
1.4.代码讲解
首先我们需要创建两个dp表，分别是f表和g表，它们的空间大小和给定的数组保持一致即可。然后让相应位置的元素进行初始化即可。
int n = nums.size();
vector<int> f(n);
vector<int> g(n);
f[0] = nums[0];
g[0] = 0;//这一句其实可以不写，因为根据vector容器的性质，此时在构造的时候就默认初始化为0了。
之后我们在通过循环来书写状态转换方程即可，此时循环的开头是从第二个位置进行的（第一个位置已经进行初始化了），然后到最后一个位置即可，之后分别填写f表和g表即可。填完表后直接返回两个表最后一个位置最大的那一个数即可。
for(int i = 1 ; i < n ; i++)
{
f[i] = g[i-1] + nums[i];
g[i] = max(f[i-1],g[i-1]);
}
return max(f[n-1],g[n-1]);
1.5.代码展示
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
vector<int> f(n);
vector<int> g(n);
f[0] = nums[0];
g[0] = 0;
for(int i = 1 ; i < n ; i++)
{
f[i] = g[i-1] + nums[i];
g[i] = max(f[i-1],g[i-1]);
}
return max(f[n-1],g[n-1]);
}
};
2.打家劫舍Ⅱ
2.1.题目来源
本题和上题一样，同样是来自于力扣，只不过比上面的那个题更复杂了一点。下面小编给出链接：213. 打家劫舍 II - 力扣（LeetCode）
2.2.题目分析
此时我们先分析一下题目，其实这个题目大体还是和上面那个题目是一样的，只不过他们两个题目显著的不同点就是，本题给定的房屋是围城一圈的，简单来说，就是首尾相连的，所以此时倘若我们想要抢劫第一家房子，那么第二个房子和最后一个房子是不可以偷取的，所以根据这个特性我们就可以知晓本题目的解题方法。
2.3.题目思路讲解
对于动态规划的题目，我们往往会设置好dp表来辅助进行做题，此时本题其实和上面的打家劫舍问题高度相似，所以我们依旧是开辟两个dp表来进行做题目，只不过我们仅仅处理一下细节问题，就可以把这个题目包装成打家劫舍问题，下面小编给各位讲解一下本题的细节。
此时我们可以清晰的知道我们这个数组是环形的，如果我们根据环形做这个题目，这个题目的难度是很大的，所以我们要学会转换思维，此时我们可以把第一个位置作为突破口，当我们选择第一个位置的时候，那么第二个位置和最后一个位置是不可以在偷取的，所以这变相的就告诉了我们此时我们需要仅仅可以选取第三个位置到倒数第二个位置进行选择；如果我们不选择偷取第一个房子，那么我们可以选择从第二个房子到倒数第一个位置进行数据的选择。此时通过第一个位置的选择与否，就可以破解本题的环形问题。此时我们在对两种状态分别进行一次打家劫舍的方法即可，此时这个就是本题的做题思路，其实只要做了打家劫舍的问题，那么它延伸的问题也是可以很快就可以解决。
2.4.代码讲解
本题首先需要确定此时给定我们的数组到底有几个房子，如果只有一个房子，那么就返回该房子的金钱，如果只有两个房子，那么返回第一个房子和第二个房子的最大值即可。
int n = nums.size();
if(n==1) return nums[0];
if(n == 2) return max(nums[0],nums[1]);
之后我们对对于是否选取一位置分别进行两次打家劫舍的分析，因为二者遵循的都是打家劫舍的分析方法，所以小编直接把打家劫舍包装成了一个函数，此时这个函数和第一个打家劫舍问题所写的函数是很像的，所以我就不细说了。
int rot(vector<int>& nums,int left,int right)
{
int n = nums.size();
vector<int> f(n + 1);
auto g = f;
f[left] = nums[left];
for(int i = left + 1 ; i <= right ; i++)
{
f[i] = g[i-1] + nums[i];
g[i] = max(f[i-1],g[i-1]);
}
return max(f[right],g[right]);
}
之后我们在主函数返回两个状态的最大值即可（即选取第一个房子和不选取第一个房子）。
return max(nums[0] + rot(nums,2,n-2),rot(nums,1,n-1));
2.5.代码展示
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if(n==1) return nums[0];
if(n == 2) return max(nums[0],nums[1]);
return max(nums[0] + rot(nums,2,n-2),rot(nums,1,n-1));
}
int rot(vector<int>& nums,int left,int right)
{
int n = nums.size();
vector<int> f(n + 1);
auto g = f;
f[left] = nums[left];
for(int i = left + 1 ; i <= right ; i++)
{
f[i] = g[i-1] + nums[i];
g[i] = max(f[i-1],g[i-1]);
}
return max(f[right],g[right]);
}
};
3.总结
本文到这里也就结束了，对于今天小编讲述的两个问题，小编希望各位读者朋友要好好掌握，因为动态规划的问题不仅仅涉及我们之后考研，还涉及到部分公司的笔试或者面试问题，只有我们储备好知识，才可以从容的面对这些问题。小编在写这篇博客的时候正值期末周，所以文章写的可能有点乱，希望各位读者见谅，我发现直到期末周才可以让人后悔为什么这学期没有好好的学知识，小编现在复习的头都快大了！如果文章有错误，可以在评论区指出，我会定时看评论来进行回复，一起写题的时光总是短暂的，那么各位大佬们，我们下一篇文章见啦！
