数组相关动态规划

algorithm

---

偷东西

• 偷东西
• 题目大意：给定一个非负数组，从左到右每次可以选择一个数，但是相邻的选择不能是近邻的两个数。求可以选择的数之和最大。

思路1

• 给定数组$[a_0,a_1\cdots a_{n-1}]$，假设对于数$a_i$，有两种结果，一种是选择，一种是不选择。如果我们选择$a_i$，我们获得的数之和是为前一次不选择$a_{i-1}$的选择结果加上这个数字，如果不选择$a_i$，我们获得的数之和，是前一次关于$a_{i-1}$选择的结果。
• 假设$dp[i]$，表示我们在$a_i$时获取的数之和，那么$dp[i]$的来源有两个，一个是$dp[i-1]$，对应没有选择$a_i$，另一个是$dp[i-2]$对应选择$a_i$
• 由于要求和最大，我们选择两者之间最大的结果作为$dp[i]$的结果。

$$dp[i] = \underset{2\le i \lt n}{max} \left\{\begin{matrix} dp[i-1]& not \ select\ a_i\\ dp[i-2] + a_i& select \ a_i \end{matrix}\right.$$

• 初始情况：$dp[0] = nums[0]$

int rob(vector<int>& nums) {
        int n = nums.size();
        if(n == 0 )
            return 0;
        vector<int> dp(n + 1,0); // dp[n]才是结果
        dp[1] = nums[0]; // 方便计算
        for(int i = 2; i <= n; i++ ) {
            dp[i] = max( dp[i-2] + nums[i-1], dp[i-1]);
        }
        return dp[n];
}

• 时间复杂度：$O(n)$，空间复杂度：$O(n)$
• 由于$dp[i]$ 只依赖于$dp[i-1],dp[i-2]$，可优化空间至$O(1)$。

---

偷东西2

• 偷东西2
• 题目大意：给定一个非负数组，从左到右每次可以选择一个数，但是相邻的选择不能是近邻的两个数，并且首尾两个数不能同时选择。求可以选择的数之和最大。

思路1

• 如果$a_0$ 被选择了，那么就不能选择$a_{n-1}$ 问题退化为$(a_0,a_1,\cdots a_{n-2})$ 中选择最大值的和
• 如果$a_0$ 没有被选择了，那么就可以选择$a_{n-1}$ 问题退化为$(a_1,\cdots a_{n-1})$ 中选择最大值的和
• 可分为两种情况，依次按照上题的思路来解决，最后选择一个大的方案

$$dp[i] = \underset{2\le i \lt n}{max} \left\{\begin{matrix} dp[i-1]& not \ select\ a_i\\ dp[i-2] + a_i& select \ a_i \end{matrix}\right. \\ res = max(dp[0\cdots ,n-2],dp[1,\cdots, n-1])$$

• 初始情况：$dp[0] = nums[0]$

int rob(vector<int>& nums) {
        int n = nums.size();
        if(n <= 0)
            return 0;
        if(n <= 1)
            return nums[0];
        vector<int> dp(n + 1, 0);
        dp[1] = nums[0]; // 
        for(int i = 2; i < n; i++ ) {
            dp[i] = max(dp[i-1], dp[i-2] + nums[i-1]);
        }
        int maxv = dp[n-1];
        dp[1] = 0;// 不选择a[0]
        for(int i = 2; i <= n; i++ ) {
            dp[i] = max(dp[i-1],dp[i-2] + nums[i-1]);
        }
        maxv = max(maxv ,dp[n]);
        return maxv;
    }

• 时间复杂度：$O(n)$，空间复杂度：$O(n)$
• 由于$dp[i]$ 只依赖于$dp[i-1],dp[i-2]$，可优化空间至$O(1)$。

---