发表于 更新于

动态规划之间隔选择问题

打家劫舍

给定一个代表每个房屋存放金额的非负整数数组，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int rob(vector<int>& nums) {
        int n=nums.size();
        int dpyes[150];
        int dpno[150];
        dpyes[0]=nums[0];
        int i;
        for(i=1;i<n;i++){
            dpyes[i]=nums[i]+dpno[i-1];
            dpno[i]=max(dpyes[i-1],dpno[i-1]);
        }
        return max(dpyes[n-1],dpno[n-1]);
    }
};

经典的动态规划问题。由于这题涉及到了间隔求和的问题，在遍历到下一个元素之前，我们不能确定前一整段的和是否为最优值，因此这里用到了两个dp数组，dpyes表示取当前的值时的能够盗窃到的最高金额，dpno表示不取当前值。

状态转移方程

1
dpyes[i]=nums[i]+dpno[i-1];

取当前值，那么上一个值就不能取了，因此等于当前的金额加上dpno[n-1]（即不偷上一家时的最大金额）`

1
dpno[i]=max(dpyes[i-1],dpno[i-1]);

不取当前值，那么上一个值就能取，同时也可以不取上一个值，因此直接两个求一个max

结论

最后直接返回dp[n-1]的最大值就行了

删除并获得点数

给你一个整数数组 nums ，你可以对它进行一些操作。

每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        int i;
        const int N=2e4+4;
        int dpyes[N];
        int dpno[N];
        int n=nums.size();
        sort(nums.begin(),nums.end());
        dpyes[0]=nums[0];
        for(i=1;i<n;i++){
            if(nums[i-1]==nums[i]-1){//两元素差值等于1
                dpyes[i]=dpno[i-1]+nums[i];
                dpno[i]=max(dpyes[i-1],dpno[i-1]);
            }
            else{
                if(nums[i-1]==nums[i]){//两元素相等
                    dpyes[i]=dpyes[i-1]+nums[i];
                    dpno[i]=dpno[i-1];
                } 
                else{//两元素不等，但差值大于1
                    dpyes[i]=max(dpyes[i-1],dpno[i-1])+nums[i];
                    dpno[i]=max(dpyes[i-1],dpno[i-1]);
                }
            }
        }
        return max(dpyes[n-1],dpno[n-1]);
    }
};

乍一看，和上面那题极其相似，实则极其相似，只不过需要加一点特殊判断，比上面略微复杂。

这题也是间隔取值，不同的是，这里的间隔的条件是值的相对差，而不是相对位置，因此两个相邻的值可能同时取，也可能不同时取。所以我们就要把判断条件改成值的相对差。这里也用到了两个dp数组，dpyes表示取当前的值时的最高点数，dpno表示不取当前值。

考虑到杂乱的数组不利于寻找删除的元素，因此直接排序一下。

状态转移方程

1
2
3
4
if(nums[i-1]==nums[i]-1){//两元素差值等于1
    dpyes[i]=dpno[i-1]+nums[i];
    dpno[i]=max(dpyes[i-1],dpno[i-1]);
}

两元素差值等于1，即不满足同时取，这里与上面类似，就不过多赘述了。

1
2
3
4
if(nums[i-1]==nums[i]){//两元素相等
    dpyes[i]=dpyes[i-1]+nums[i];
    dpno[i]=dpno[i-1];
}

两元素相等，那么如果取元素的话，就要继承上一个元素的和并加上这个元素的值，不去的话也要继承上一个元素的值，以便后面能够“回溯”到不取某一段序列的最大点数初始值。

1
2
3
4
else{//两元素不等，但差值大于1
    dpyes[i]=max(dpyes[i-1],dpno[i-1])+nums[i];
    dpno[i]=max(dpyes[i-1],dpno[i-1]);
}

两元素不等，但差值大于1，说明前后能同时取。所以我们就要在前一个的yes和no中选一个最大值，然后加上或不加上当前的值。

最后返回dp[n-1]的最大值即可。