算法沉淀 —— 动态规划篇（简单多状态dp问题上）

前言

几乎所有的动态规划问题大致可分为以下5个步骤，后续所有问题分析都将基于此

• 1.、状态表示：通常状态表示分为以下两种，其中更是第一种为主。

  • 以i为结尾，dp[i] 表示什么，通常为代求问题（具体依题目而定）
  • 以i为开始，dp[i]表示什么，通常为代求问题（具体依题目而定）

• 2、状态转移方程

  • 以上述的dp[i]意义为根据， 通过最近一步来分析和划分问题，由此来得到一个有关dp[i]的状态转移方程。

• 3、dp表创建，初始化

  • 动态规划问题中，如果直接使用状态转移方程通常会伴随着越界访问等风险，所以一般需要初始化。而初始化最重要的两个注意事项便是：保证后续结果正确，不受初始值影响；下标的映射关系。
  • 而初始化一般分为以下两种：
    • 直接初始化开头的几个值。
    • 一维空间大小+1，下标从1开始；二维增加一行/一列。

• 4、填dp表、填表顺序：根据状态转移方程来确定填表顺序。

• 5、确定返回值

一、按摩师

【题目链接】：面试题 17.16. 按摩师
【题目】：

一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。

【分析】：
 我们定义dp[i]表示从[0, 1]按摩师能找到的最优预约集合。但我们发现第i个位置还可以细分为两种情况：i号预约、i号不预约。因此我们进一步分析定义f[i]表示从开始到i位置，并且i号预约的最优集合；g[i]表示从开始到i位置，并且i号不预约的最优集合。
 其中 f[i] = g[i - 1] + nums[i - 1]、g[i] = max(g[i - 1], f[i - 1])。
【代码编写】：

class Solution {
public:
    int massage(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n + 1);//f[i]表示[1, i]之间， 并且i号预约的最优集合
        vector<int> g = f;//g[i]表示[1, i]之间，并且i号不预约的最优集合
        //填表
        for(int i = 1; i <= n; i++)
        {
            g[i] = max(g[i - 1], f[i - 1]);
            f[i] = g[i - 1] + nums[i - 1];
        }
        return max(f[n], g[n]);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

二、打家劫舍 II

【题目链接】：LCR 090. 打家劫舍 II
【题目】：

 一个专业的小偷，计划偷窃一个环形街道上沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
 给定一个代表每个房屋存放金额的非负整数数组 nums ，请计算 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

【实例】：

输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

【分析】：
 显然题目中所有房屋形成了一个类似于环形结构，比较棘手。所以我们可以以1号房屋是否被偷进行分类讨论，将环形结构蜕变成普通数组，首尾不影响。
 分类情况：因为房屋不能连续被偷。所以：

1. 如果1号房屋不被偷，此时模型简化为偷[2, n]号房屋，首位不影响。
2. 如果1号房屋被偷，此时意味着2号和n号房屋一段不被偷，此时模型简化为偷[3, n-1]号房屋，首位不影响。最后结果假设1号房屋所偷金额即可。

 上述两种情况统一为偷[begin, end]号的房屋，相邻房屋不能都被偷。此时我们可以定义dp[i]表示小偷在[begin, i]号房屋间所偷的最大金额。当我们发现i位置还可细分为偷以不透。所以我们继续细分情况，定义f[i]表示小偷在[begin, i]之间，且i号房屋被偷的最大金额；g[i]表示小偷在[begin, i]之间，且i号房屋不被偷的最大金额。
 此时f[i]的最近一步时，i-1号房屋不被偷，i号房屋被偷的最大金额，所以发f[i]的状态转移方程为f[i] = g[i-1] + nums[i-1];对于g[i]来说，此时有两种情况，i-1号房屋被偷和不被偷的最大金额，所以g[i]的状态转移方程为g[i] = max(f[i - 1], g[i - 1]。最后比较f[n],g[n]，返回最大值即可。

【代码编写】：

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        return max(_rob(nums, 2, n), _rob(nums, 3, n - 1) + nums[0]);
    }

    int _rob(vector<int>& nums, int begin, int end)
    {
        int n = nums.size();
        vector<int> f(n + 1);//f[i]表示[begin, i]号房屋中，i号房屋偷，偷窃到的最高金额
        vector<int> g = f;//g[i]表示[begin, i]号房屋中，i号房屋不偷，偷窃到的最高金额
        for(int i = begin; i <= end; i++)
        {
            f[i] = g[i - 1] + nums[i - 1];
            g[i] = max(f[i - 1], g[i - 1]);
        }
        return max(f[end], g[end]);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

三、删除并获得点数

【题目链接】：740. 删除并获得点数
【题目】：

 给你一个整数数组 nums ，你可以对它进行一些操作。
每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
 开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

【实例】：

输入：nums = [2,2,3,3,3,4]
输出：9
解释：
删除 3 获得 3 个点数，接着要删除两个 2 和 4 。
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
总共获得 9 个点数。

【分析】：
 我们可以向通过一个数组hash，将原数组中所有相同元素(假设为x)的值累加后(假设结果为sum)，存放到hash中（下标为x, hash[x] = sum）。
 通过第一步，我们可以将原问题转化为：在hash数组中，相邻元素的值不能同时获取，求最终所获得的点数的最大值!
 我们定义f[i]表示在[0, i]中获取点数，并且保证hash[i]的元素被获取，最终所能获得的最大点；g[i]表示在[0, i]中获取点数，并且保证hash[i]的元素不被获取，最终所能获得的最大点数。可得状态转移方程为：f[i] = g[i - 1] + hash[i];、g[i] = max(f[i - 1], g[i - 1])！
 从左往右依次填dp表后，返回结果最大值！
【代码编写】：

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        const int N = 10001;
        int hash[N] = {0};
        for(auto x : nums)
            hash[x] += x;
        vector<int> f(N);//f[i]表示从[1, i],i位置对应点数被获得，所获得的最大点数
        vector<int> g = f;//g[i]表示从[1, i],i位置对应点数不被获得，所获得的最大点数
        for(int i = 1; i < N; i++)
        {
            f[i] = g[i - 1] + hash[i];
            g[i] = max(f[i - 1], g[i - 1]);
        }
        return max(f[N - 1],g[N - 1]); 
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

四、粉刷房子

【题目链接】：LCR 091. 粉刷房子
【题目】：

 假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
 当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。
 例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。
 请计算出粉刷完所有房子最少的花费成本。

【实例】：

输入: costs = [[17,2,17],[16,16,5],[14,3,19]]
输出: 10
解释: 将 0 号房子粉刷成蓝色，1 号房子粉刷成绿色，2 号房子粉刷成蓝色。
最少花费: 2 + 5 + 3 = 10。

【分析】：
 我们可以定义dp[i]表示粉刷[0, i]号房子，并且相邻房子颜色不同，其花费的最少成本。但我们发现i号防止可以细分为刷成红色、蓝色、绿色。

 所以我们可以使用一个二维数组，其中dp[i][0]表示粉刷[0, i]号房子，且i号房子为蓝色的最小花费；dp[i][1]表示粉刷[0, i]号房子，且i号房子为绿色的最小花费；dp[i][0]表示粉刷[0, i]号房子，且i号房子为红色的最小花费！！

 显然状态转移方程为： dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0]、dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1]、dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i - 1][2];

 从左往右依次填表，最后比较dp[n][0]、dp[n][1]、dp[n][2]的最小值即可！
【代码编写】：

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        int n = costs.size();
        vector<vector<int>> dp(n+1, vector<int>(3));
        //dp[i][0]表示粉刷[0, i]号房子，且i号房子为蓝色的最小花费
        //dp[i][1]表示粉刷[0, i]号房子，且i号房子为绿色的最小花费
        //dp[i][2]表示粉刷[0, i]号房子，且i号房子为红色的最小花费
        for(int i = 1; i <= n; i++)
        {
            dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0];
            dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1];
            dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i - 1][2];
        }
        return min(dp[n][0], min(dp[n][1], dp[n][2]));
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17