动态规划 —— dp 问题-删除并获得点数

1. 删除并获得点数

题目链接：

740. 删除并获得点数 - 力扣（LeetCode）https://leetcode.cn/problems/delete-and-earn/description/

 

---

2. 题目解析

先创建一个arr数组，将原数组nums里的值全部映射到arr数组中，因为nums里的值可能是相邻而不相连，但是一维数组的下标是连续的，然后我们可以使用arr[i]来表示：i这个数出现次数的总和

将数组中的数统计到arr中，然后在arr中进行一次“打家劫舍问题”

---

3.  算法原理 

状态表示：以某一个位置为结尾或者以某一个位置为起点

   

dp[i]表示：选到i位置的时候，此时的最大点数分两种情况：

    

        1.f[i]表示：选到i位置的时候，当前位置nums[i]必选，此时的最大点数

    

        2.g[i]表示：选到i位置的时候，当前位置nums[i]不选，此时的最大点数

2. 状态转移方程

  

根据最近的一步来划分问题：

   

到达dp[i]有两种情况：

    

  1. f[i]=g[i-1] + arr[i]

   

2. g[i]：a. 当选择i-1的位置时：f[i-1]

    

              b.当不选择i-1的位置时：g[i-1]

    

              g[i]=max(f[i-1],g[i-1])

3. 初始化 ：把dp表填满不越界，让后面的填表可以顺利进行

    

本题初始化为：f[0]=arr[0]    g[0]=0

4. 填表顺序 

    

本题的填表顺序是：从左往右，两个表一起填

5. 返回值 ：题目要求 + 状态表示 

    

偷到最后一个位置分为两种情况：选和不选

本题的返回值是：max(f[N-1],g[N-1])

---

4.代码

动态规划的固定四步骤：1.  创建一个dp表

                                        2. 在填表之前初始化

                                        3. 填表（填表方法：状态转移方程）

                                        4. 确定返回值 

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        //预处理
        const int N = 10001;
        int arr[N] = { 0 };
        //进行映射，将nums里的值映射到arr数组里
        for (auto x : nums) arr[x] += x;

        //开始打家劫舍问题
        //1.  创建一个dp表
        vector<int>f(N);
        auto g = f;

        //本题不需要初始化，因为我们是要把f[0]=arr[0]和g[0]=0，
        //但是vector默认为0，所以不用初始化

        //3. 填表（填表方法：状态转移方程）
        //0位置的值已经初始化为0，所以从1开始,填表到最大值N
        for (int i = 1; i < N; i++)
        {
            f[i] = g[i - 1] + arr[i];
            g[i] = max(f[i - 1], g[i - 1]);
        }
        //4. 确定返回值 
        return max(f[N - 1], g[N - 1]);

    }
};

---

未完待续~

原文地址：https://blog.csdn.net/hedhjd/article/details/143584797

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！