star2dust

每天进步一点点

首页 归档 标签 关于 博客 论文复现 工具箱

【力扣刷题】动态规划问题的思考与总结

2021-07-21 41 min read # Algorithm

什么是动态规划

动态规划（英语：Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

  • 什么样的题目需要用动态规划？

动态规划要解决的都是一些问题的最优解，即从很多解决问题的方案中找到最优的一个。以力扣动态规划专题为例，题目都是形如最长数组长度、最小花费、最大和等。当我们在求一个问题最优解的时候，可以把这个问题分解成多个子问题，然后递归地找到每个子问题的最优解，最后通过一定的数学方法对各个子问题的最优解进行组合得出最终的结果。总结来说就是一个问题的最优解是由它的各个子问题的最优解决定的。

将子问题的解进行组合可以得到原问题的解是动态规划可行性的关键。即存在最优子结构，实际上不一定所有的问题的解都能被直接写为子问题的组合。在解题中一般用状态转移方程描述这种组合。例如原问题的解为f(n)f(n)，即状态。状态转移方程形如f(n)=f(n−1)+f(n−2)f(n) = f(n - 1) + f(n - 2)，即斐波拉契数列递推公式，描述了一种原问题与子问题的组合关系 。找到了最优子结构，也就能推导出一个状态转移方程f(n)f(n)，通过这个状态转移方程，我们能很快的写出问题的递归实现方法。

  • 为什么不用递归？

当我们在递归地寻找每个子问题的最优解的时候，有可能会重复地遇到一些更小的子问题，而且这些子问题会重叠地出现在子问题里，出现这样的情况，会有很多重复的计算，动态规划可以保证每个重叠的子问题只会被求解一次。当重复的问题很多的时候，动态规划可以减少很多重复的计算。

去掉重复子问题不是保证解的正确性必须的，但是如果递归求解子问题时，没有出现重复子问题，则没有必要用动态规划，直接普通的递归就可以了。

  • 解决动态规划问题的核心

解决动态规划问题的核心是找出子问题及其子问题与原问题的关系。

动态规划算法中关于最优子结构和重复子问题的理解的关键点：

  1. 证明问题的方案中包含一种选择，选择之后留下一个或多个子问题；
  2. 设计子问题的递归描述方式；
  3. 证明对原问题的最优解包括了对所有子问题的最优解；
  4. 证明子问题是重叠的（这一步不是动态规划正确性必需的，但是如果子问题无重叠，则效率与一般递归是相同的）。

解决动态规划问题的步骤

动态规划有两种计算顺序，一种是自顶向下的、使用备忘录（记忆化）的递归方法，一种是自底向上的、使用DP数组（滚动数组）的循环方法。不过在普通的动态规划题目中，99% 的情况我们都不需要用到备忘录方法，所以我们最好坚持用自底向上的DP数组。同时备忘录方法的空间复杂度会比较高。

  • 自顶向下

递归的解法需要非常多的重复计算，如果有一种办法能避免这些重复计算，可以节省大量计算时间。记忆化就是基于这个思路的算法。在递归地求解子问题f(1)f(1)，f(2)f(2)... 过程中，将结果保存到一个表里，在后续求解子问题中如果遇到求过结果的子问题，直接查表去得到答案而不计算。

  • 自底向上

有了状态转移方程，我们就知道如何从最小的问题规模入手，然后不断地增加问题规模，直到所要求的问题规模为止。在这个过程中，我们可以从小到大记忆每个问题规模的解来避免重复的计算。这种方法就是自底向上的方法，由于避免了递归，这是一种更好的办法。

但是迭代法需要有一个明确的迭代方向，例如线性，区间，树形，状态压缩等比较主流的动态规划问题中，迭代方向都有相应的模式。但是有一些问题迭代法方向是不确定的，这时可以退而求其次用记忆化来做。

动态规划自底向上的四个解题步骤是：

  1. 定义子问题
  2. 写出子问题的递推关系
  3. 确定 DP 数组的计算顺序
  4. 空间优化（可选）

基础递推算法

本节总结了各类利用DP数组自底而上的算法，以子问题递推关系分类。

子问题求和

最简单的递推关系就是后一个子问题等于前几个子问题求和，如509. 斐波那契数、1137. 第 N 个泰波那契数。这两个问题大家都会，这里不再赘述，需要注意的是最小的几个子问题需要特判。

除了编程题以外，斐波拉契数列和泰波拉契数列是大厂笔试找规律题的常客，通常换掉头几项，但递推关系一样。

1，3，4，7，11，18，29，……（斐波拉契）

1，3，5，9，17，31，57，……（泰波拉契）

下面列出了几个子问题求和的典型问题。

爬楼梯

【爬楼梯】这类题和斐波拉契数列解法完全相同，高阶一点的还有【最小花费爬楼梯】。

70. 爬楼梯：假设你正在爬楼梯。需要nn阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

class Solution {
public:
    int climbStairs(int n) {
        //注意特判！！
        if (n < 3){
            return n;
        }
        //只记录f(n-1)和f(n-2)两个状态
        //注意：只记录两个状态比递归时间复杂度低，是因为递归计算f(n-1)时重复计算了f(n-2)
        int ans, a = 1, b = 2;
        for (int i = 3; i <= n; i++){
            ans = a + b;
            a = b;
            b = ans;
        }
	    return ans; 
    }
};

746. 使用最小花费爬楼梯：数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值cost[i]（下标从 0 开始）。每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。

请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
       int n = cost.size();//注意：顶层是n+1
        int a = 0, b = 0;//a、b初始化为到0、1阶梯的最低花费
        for (int i = 2; i <= n; i++){//顶层是n+1，所以i<=n要取等
            int next = min(a + cost[i - 2], b + cost[i - 1]);//计算下一阶梯的最低花费
            a = b;
            b = next;
        }
        return b; //返回next
    }
};

杨辉三角

【杨辉三角】这类题要注意两点，一是数组首尾不满足递推关系，二是可以把上层数组复制用于计算下层。

118. 杨辉三角：给定一个非负整数 numRows，生成「杨辉三角」的前 numRows行。注意：1<=numRows<=30

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ans;
        for (int i=0;i<numRows;i++){
            //getRow()计算杨辉三角的每一行元素，定义见【杨辉三角II】
            ans.push_back(getRow(i));
        }
        return ans;
    }
};

119. 杨辉三角 II：给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。注意：0<=rowIndex<=33

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

为了便于理解，这里把杨辉三角写成直角三角形：

row[0]：1

row[1]：1，1

row[2]：1，2，1

row[3]：1，3，3，1

row[4]：1，4，6，4，1

……

注意到，row[n-1]到row[n]的步骤是：

  1. row[n]初始化为：{row[n-1],1}；
  2. 从j=n-1开始一直到j=1，每个元素更新为row[n][j]=row[n][j]+row[n][j-1]。
class Solution {
public:
    vector<int> getRow(int rowIndex) {
        int n = rowIndex + 1; //第k行有k+1个元素
        vector<int> res{ 1 }; //每行第一个元素一定是1，第0行只有一个1
        //注意vector的赋值方法：res{a,b,c,d,...}，即res={a,b,c,d,...}
        for (int i = 1; i < n; i++){//从第1行开始
            res.push_back(1); //每一行最后一个元素一定是1
            for (int j = i - 1; j >= 1; j--){//每一行只用改变中间元素，中间元素是上一行（i-1）相邻元素之和
                res[j] = res[j] + res[j - 1];
            }
        }
        return res;
    }
};

子问题最值

另一种常见递推关系是后一个子问题等于前几个子问题的最值，典型的问题是【打家劫舍】和【最大子序和】。

198. 打家劫舍：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

本题对状态的选择可以说是这类问题的一个通用选法，即定义dp[i]dp[i]为[0,i][0,i]房屋中能偷到的最高金额，注意这里选择ii​作为右边界。

递推关系为：

dp[i]=max⁡(dp[i−2]+nums[i],dp[i−1])dp[i]=\max(dp[i-2]+nums[i],dp[i-1])

即要么偷[0,i−2]+i[0,i-2]+i，要么偷[0,i−1][0,i-1]，二者取最大值。

class Solution {
public:
    int rob(vector<int>& nums) {
         //自底而上计算
        int a = 0, b = 0;
        //假设前面多了两个房子，里面金额为0，那么不影响最后结果
        for (int i : nums){
            //房屋相邻关系[a,b,i]，偷a+i和b较大的
            int next = max(b, a + i);
            a = b;
            b = next;
        }
        return b;
    }
};

最大子序和

根据不同问题要求，迭代过程中有时需要返回所有子问题最值，即打擂维护最值。

53. 最大子序和：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

类似上一题，我们定义dp[i]dp[i]为以第ii​个数结尾的连续子数组最大和，那么递推关系为

dp[i]=max⁡(dp[i−1]+nums[i],nums[i])dp[i]=\max(dp[i-1]+nums[i],nums[i])

即要么[0,i][0,i]作为一个连续子数组，要么ii单独做一个连续子数组。

此外，对于求最大子序和，有一个通用解法：【kadane算法】。为了讲解该算法原理，同样定义dp[j]dp[j]​为以第jj​​个数结尾的连续子数组最大和，写成数学表达式为

dp[j]=max⁡i(nums[i]+nums[i+1]+⋯+nums[j])dp[j] = \max_i(nums[i]+nums[i+1]+\cdots+nums[j])

那么dp[j]dp[j]与dp[j−1]dp[j-1]的关系可以分类讨论，如果nums[j]≥0nums[j]\geq 0，那么dp[j−1]dp[j-1]加上它肯定不会小于自己，此时dp[j]=dp[j−1]+nums[j]dp[j]=dp[j-1]+nums[j]；如果nums[j]<0nums[j]<0，那么dp[j−1]dp[j-1]加上它会变小，因此不加它，即dp[j]=dp[j−1]dp[j]=dp[j-1]。

综上所述​，递推关系为

dp[i]=dp[i−1]+max⁡(nums[i],0)dp[i]=dp[i-1]+\max(nums[i],0)

上面这两种算法是等价的。

int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    int pre = 0, rmax = nums[0];
    for (int i = 0; i < n; i++){//f(i)表示以第i个数结尾的“连续子数组最大和”
        //i-1结尾的最大和+nums[i]和仅一个nums[i]比较大小
        pre = max(pre + nums[i], nums[i]); //f(i)=max(f(i-1)+nums[i],nums[i])
        //f(i)=nums[i]+max(f(i-1),0)是另一种写法（kadane算法），如果f(i-1)是正的，则相加必然更大，否则从i重新开始
        rmax = max(pre, rmax); //打擂维护最大和
    }
    return rmax;
}

1014. 最佳观光组合：给你一个正整数数组 values，其中 values[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的 距离 为 j - i。一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，也就是景点的评分之和 减去 它们两者之间的距离。返回一对观光景点能取得的最高分。

int maxScoreSightseeingPair(vector<int>& values) {
    int n = values.size();
    //curr是以i为右边界的数组中最高景点得分
    int curr = values[1] + values[0] - 1, vmax = curr;
    for (int i = 2; i < n; i++){
        //令curr是[l,i-1]，那么下一步最高分要么是[l,i]，要么是[i-1,i]
        //[l,i-1]怎么办？上一轮比过了！
        curr = max(curr + values[i] - values[i - 1] - 1, values[i] + values[i - 1] - 1);
        vmax = max(curr, vmax);
    }
    return vmax;
}

官方题解用了另一种思路：对于每一个j而言，values[j]-j是固定的，那么以j为右边界的最大得分取决于values[i]+i。那么只需要一次遍历，每次找到最大values[i]+i即可。

int maxScoreSightseeingPair(vector<int>& values) {
    int n = values.size();
    //imax为最大values[i]+i
    int imax = values[0] + 0, vmax = 0;
    for (int j = 1; j < n; j++){
        vmax = max(values[j] - j + imax, vmax);//维护最高得分（前一个维护要返回的最优解）
        imax = max(values[j] + j, imax);//维护最大imax（后一个维护j之前的子问题最值）
    }
    return vmax;
}

这一思路同样可以用于【买卖股票的最佳时机】（只能买卖一次）。

121. 买卖股票的最佳时机：给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

int maxProfit(vector<int>& prices) {
	int n = prices.size();
    if (n<2) return 0;//注意特判，有些测试用例会给一些特殊情况
	int pmin = prices[0], rmax = 0;
	for (int i = 1; i < n; i++){
		rmax = max(rmax, prices[i] - pmin);//维护利润最大值（pmin是所有以前天数价格最小值）
		pmin = min(pmin, prices[i]);//维护买入价格最小值
	}
	return rmax;
}

二维DP数组

对于【不同路径】这样的题，无法仅用两三个变量维护子问题状态，需要用到二维DP数组。

62. 不同路径：一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

class Solution {
public:
    int uniquePaths(int m, int n) {
        //定义dp数组
        vector<vector<int>> dp(m,vector<int>(n));
        //特判，如果行或者列为1，则路径只有1条
        for (int i = 0; i < m; i++){
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++){
            dp[0][i] = 1;
        }
        //动态规划
        for (int i = 1; i < m; i++){
            for (int j = 1; j < n; j++){
                //机器人只能向下或者向右移动一步，故需要维护两个状态，即左方和上方
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
};

1143. 最长公共子序列: 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.length(), n = text2.length();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; i++) {
            char c1 = text1.at(i - 1);
            for (int j = 1; j <= n; j++) {
                char c2 = text2.at(j - 1);
                if (c1 == c2) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
};

1035. 不相交的线: 在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。

现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足满足：

  • nums1[i] == nums2[j]

  • 且绘制的直线不与任何其他连线（非水平线）相交。

请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。

以这种方法绘制线条，并返回可以绘制的最大连线数。

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        // dp[i][j]表示num1[0:i]和num2[0:j]的最大公共子序列长度（左闭右开）
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; i++) {
            int num1 = nums1[i - 1];
            for (int j = 1; j <= n; j++) {
                int num2 = nums2[j - 1];
                //如果是公共元素则加1
                if (num1 == num2) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
};

非最优子结构

有些问题没有最优子结构，无法通过子问题的组合得到递推关系，但是也能通过维护多个状态的思想来应用动态规划算法。通常问题是带有交替符号特性的，还要注意存temp以避免变量覆盖。

152. 乘积最大子数组：给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

如果我们用【最大子序和】的经验，可以得到dp[i]=max⁡(dp[i−1]∗nums[i],nums[i])dp[i]=\max(dp[i-1]*nums[i],nums[i])​，但在这里是错的，为什么呢？

因为这里的定义并不满足「最优子结构」，当前位置的最优解未必是由前一个位置的最优解转移得到的，即乘法会变符号，最大值可能下一步变成最小值，那么需要用两个DP数组同时维护最大值和最小值，如果变号就乘最小值，未变号就乘最大值。

int maxProduct(vector<int>& nums) {
	//pmax:以i为右边界乘积最大值，pmin:以i为右边界乘积最小值（可能是负的）
	int pmax = nums[0], pmin = nums[0], ans = nums[0];
	for (int i = 1; i < nums.size(); ++i) {
		int mx = pmax, mn = pmin; //存temp避免变量覆盖
		//最大值有3种可能：1. pmax*nums[i]; 2. pmin*nums[i]; 3. nums[i]
		pmax = max(mx * nums[i], max(nums[i], mn * nums[i]));
		pmin = min(mn * nums[i], min(nums[i], mx * nums[i]));
		ans = max(pmax, ans);
	}
	return ans;
}

1567. 乘积为正数的最长子数组长度：给你一个整数数组nums ，请你求出乘积为正数的最长子数组的长度。一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。请你返回乘积为正数的最长子数组长度。

int getMaxLen(vector<int>& nums) {
	int n = nums.size();
	//pos:以i为右边界乘积为正的最长子数组长度，neg:以i为有边界乘积为负的最长子数组长度
	int pos = (nums[0] > 0), neg = (nums[0] < 0); 
	//题目要求乘积为正，故lmax=pos
	int lmax = pos;
	for (int i = 1; i < n; i++){
		if (nums[i]>0){
			//如果nums[i]>0，则不改变符号，pos自加1，neg>0加1，==0不变
			pos = pos + 1;
			neg = neg > 0 ? neg + 1 : 0;
		}
		else if (nums[i] < 0){
			//如果nums[i]<0，则改变符号，和上面以相反方式赋值
			int pos_temp = neg>0 ? neg + 1 : 0;//存temp避免变量覆盖
			int neg_temp = pos + 1;
			pos = pos_temp;
			neg = neg_temp;
		}
		else{
			pos = 0, neg = 0;
		}
		lmax = max(lmax, pos);
	}
	return lmax;
}

买卖股票（多状态递推）

有些复杂问题不只有一种状态，每一种状态都有相应的子问题递推关系，最后返回所有状态中的最值。

详见力扣平台上的股票类型的题目：

122. 买卖股票的最佳时机 II：给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

int maxProfit2(vector<int>& prices) {
	int n = prices.size();
	if (n < 2) return 0;
	int p0 = -prices[0], p1 = 0;//两种状态
    //p0：持有股票时最大利润
    //p1：不持有股票时最大利润
	for (int i = 0; i < n; i++){
		int p0_temp = max(p0, p1 - prices[i]);//继续持有或买入
		int p1_temp = max(p1, p0 + prices[i]);//继续不持有或卖出
		p0 = p0_temp;
		p1 = p1_temp;
	}
	return p1;//最后持有不卖没有意义，只需返回不持有时最大利润
}

309. 最佳买卖股票时机含冷冻期：给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

  • 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
  • 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
int maxProfit5(vector<int>& prices) {
	int n = prices.size();
	if (n < 2) return 0;
	int p0 = -prices[0], p1 = 0, p2 = 0;//三种状态
	// p0: 手上持有股票的最大收益
	// p1: 手上不持有股票，并且当天结束时处于冷冻期中的累计最大收益（i天卖出）
	// p2: 手上不持有股票，并且当天结束时不在冷冻期中的累计最大收益（i-1天及之前卖出）
	for (int i = 1; i < n; i++){
		int p0_temp = max(p2 - prices[i], p0);//i天买入或者继续持有
		int p1_temp = p0 + prices[i];//i天卖出
		int p2_temp = max(p1, p2);//继续不持有
		p0 = p0_temp, p1 = p1_temp, p2 = p2_temp;
	}
	return max(p1, p2);//最后持有不卖没有意义，只需返回不持有时最大利润
}

714. 买卖股票的最佳时机含手续费：给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

int maxProfit6(vector<int>& prices, int fee) {
    //此题和122几乎一模一样，唯一的区别在于手续费，这里假设每次卖出时收费
	int n = prices.size();
	if (n < 2) return 0;
	int p0 = -prices[0], p1 = 0;//两种状态
    //p0：持有股票的最大收益
    //p1：不持有股票的最大收益
	for (int i = 0; i < n; i++){
		int p0_temp = max(p0, p1 - prices[i]);//继续持有或买入
		int p1_temp = max(p1, p0 + prices[i] - fee);//继续不持有或卖出，卖出时收手续费
		p0 = p0_temp;
		p1 = p1_temp;
	}
	return p1;//返回不持有时最大利润
}

打家劫舍（分治算法）

分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

动态规划问题可以表示为多个子问题的组合，如果子问题同样也是动态规划问题，且解法相同，则可以用分治法。一般情况下，除非子问题很明显是已经解决过的老问题，尽量不考虑分治。

详见力扣平台的打家劫舍类型题目：

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

int rob2(vector<int>& nums) {
    int n = nums.size();
    //特判
    if (n == 1){
        return nums[0];
    }
    else if (n == 2){
        return max(nums[0], nums[1]);
    }
    //因为0和n-1不能同时偷，根据n-1偷不偷，将问题分解为[0,n-2]和[1,n-1]两个打家劫舍问题
    return max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
}
int robRange(vector<int>& nums, int start, int end){
    //带范围的打家劫舍问题
    int a = 0, b = 0;
    for (int i = start; i <= end; i++){
        int next = max(b, a + nums[i]);
        a = b;
        b = next;
    }
    return b;
}

918. 环形子数组的最大和：给定一个由整数数组 A 表示的环形数组 C，求 C 的非空子数组的最大可能和。在此处，环形数组意味着数组的末端将会与开头相连呈环状。（形式上，当0 <= i < A.length 时 C[i] = A[i]，且当 i >= 0 时 C[i+A.length] = C[i]）此外，子数组最多只能包含固定缓冲区 A 中的每个元素一次。（形式上，对于子数组 C[i], C[i+1], ..., C[j]，不存在 i <= k1, k2 <= j 其中 k1 % A.length = k2 % A.length）

int maxSubarraySumCircular(vector<int>& nums) {
	int dp = nums[0];      //初始化dp，以i结尾的最大子序列和
	int smax = dp;         //非环最大子序列和
	int sum = dp;          //整个数组的和
	//求最大子序列和，见53题，kadane算法
	for (int i = 1; i < nums.size(); i++) {
		dp = nums[i] + max(dp, 0);
		smax = max(dp, smax);
		sum += nums[i];//附加了一个整个数组求和，故不能直接调用53
	}
	//整个数组总和是一定的，减掉[1,n-2]范围最小子序列和，剩下两头部分首尾相连，即为环最大子序列和
	int smin = 0;
	dp = nums[0]; //这里是0，后面计算1时需要该值，不代表序列从0计算
	for (int i = 1; i < nums.size() - 1; i++) {
		dp = nums[i] + min(dp, 0);
		smin = min(dp, smin);
	}
	//环最大子序列和要么是非环最大子序列和，要么是整个数组的和减[1,n-2]最小序列和
	return max(sum - smin, smax);
}

环最大子序列和要么是非环最大子序列和，要么是整个数组的和减[1,n-2]最小序列和，如下图所示（图片来自力扣）。

  • 不同时包括0和n-1，环最大子序列和是非环最大子序列和，即53题；
  • 同时包括0和n-1，环最大子序列和是整个数组的和减[1,n-2]最小序列和，因为整个数组总和是一定的，令中间[1,n-2]范围子序列和最小，再减掉，剩下两头部分首尾相连，即为环最大子序列和。

值得一提的是，有些问题可以经过数据结构转换变成已解决过的动态规划问题。

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

//删除相邻元素的操作，有没有似曾相识
//其实就是相邻房屋不能偷
int deleteAndEarn(vector<int>& nums) {
    int nmax = 0;
    for (int i : nums){
        nmax = max(nmax, i);
    }
    //求数组最大点数（房屋最大编号）
    vector<int> all(nmax + 1);
    for (int i : nums){
        all[i] += i; //同点数的元素点数求和（总金额）放在点数对应编号的房屋里
    }
    return rob(all);//跑一遍打家劫舍
}

贪心算法

前面讲了常规的子问题递推方法，下面讲贪心算法。核心思路是，在递推的同时，尽可能保证最大化目标。

55. 跳跃游戏：给定一个非负整数数组nums，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。

在本问题中，如果能到达某个位置，那一定能到达它前面的所有位置。对于任意y，只要存在一个x，使得跳跃最大长度x+nums[x]大于等于y，那么y必然可以到达。这样以来，我们依次遍历数组中的每一个位置，并实时维护最远可以到达的位置。对于当前遍历到的位置x，如果它在最远可以到达的位置的范围内，那么我们就可以从起点通过若干次跳跃到达该位置，因此我们可以用x+nums[x]更新最远可以到达的位置。遍历的过程中，如果最远可以到达的位置大于等于数组中的最后一个位置，那就说明最后一个位置可达，我们就可以直接返回 True 作为答案。反之，如果在遍历结束后，最后一个位置仍然不可达，我们就返回 False 作为答案。

bool canJump(vector<int>& nums) {
	int n = nums.size(), far = 0; //找到最远能到达的点far
	for (int i = 0; i <= far; i++){//如果i在最远可以到达的点范围内
		far = max(far, i + nums[i]);//每到一个位置更新最远能到达的点
		if (far >= n - 1){//最远位置超过n-1即成功
			return true;
		}
	}
	return false;
}

45. 跳跃游戏 II：给你一个非负整数数组 nums ，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。假设你总是可以到达数组的最后一个位置。

在本问题中，我们「贪心」地进行正向查找，找到可到达的最远位置x，在[0,x]之间遍历维护下一步能到达的最远位置y，遍历完毕更新边界为[x,y]并将跳跃次数增加 1，重复遍历过程，直到新的右边界大n-1。

int jump(vector<int>& nums) {
	int n = nums.size(), far = 0, end = 0, cnt = 0;
	for (int i = 0; i < n - 1; i++){//遍历到n-2避免最后重复跳一次（nums[n-2]必大于0）
		if (far >= i){
			far = max(far, i + nums[i]);//一跳最远距离
			if (i == end){//如果到了右边界end，更新end=far，上一次的end变成左边界）
				end = far;
				cnt++;//保证最少跳跃次数，i遍历到end之前只跳一次
			}
		}
	}
	return cnt;
}

利用贪心算法，我们也可以给买卖股票问题提供一个新的思路。

122. 买卖股票的最佳时机 II：给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）

int maxProfit2(vector<int>& prices) {
	int n = prices.size();
	int rmax = 0;
	for (int i = 1; i < n; i++){
		if (prices[i] - prices[i - 1] > 0){//只要股票涨一天就加上一天收益，不涨就在前一天卖掉
			rmax += prices[i] - prices[i - 1];
		}
	}
	return rmax;
}

背包问题

322. 零钱兑换：给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

本题中定义F(S)F(S)为凑成金额SS的最少硬币数量，我们注意到这个问题有一个最优的子结构性质，这是解决动态规划问题的关键。最优解可以从其子问题的最优解构造出来。如何将问题分解成子问题？假设我们知道 F(S)F(S)​，即组成金额 SS 最少的硬币数，最后一枚硬币的面值是 CC。那么由于问题的最优子结构，转移方程应为：

F(S)=F(S−C)+1F(S)=F(S-C)+1

但我们不知道最后一枚硬币的面值是多少，所以我们需要枚举每个硬币面额值，并选择其中的最小值。下列递推关系成立：

F(S)=min⁡i=0,…,n−1F(S−Ci)+1s.t.S−Ci>0F(S)=\min_{i=0,\dots,n-1} F(S-C_i)+1\quad s.t.\quad S-C_i>0

当S=0S=0时，F(S)=0F(S)=0；当n=0n=0时，F(S)=−1F(S)=-1​。

为了避免重复的计算，我们将每个子问题的答案存在一个DP数组中进行记忆化，如果下次还要计算这个问题的值直接从数组中取出返回即可，这样能保证每个子问题最多只被计算一次。

时间复杂度：O(Sn)O(Sn)，其中 SS 是金额，nn 是面额数。我们一共需要计算 SS 个状态的答案，且每个状态 F(S)F(S) 由于上面的记忆化的措施只计算了一次，而计算一个状态的答案需要枚举 nn 个面额值，所以一共需要 O(Sn)O(Sn) 的时间复杂度。
空间复杂度：O(S)O(S)，我们需要额外开一个长为 SS 的数组来存储计算出来的答案 F(S)F(S)。

class Solution {
    vector<int>count;//DP数组
    int dp(vector<int>& coins, int rem) {
        //特判
        if (rem < 0) return -1;
        if (rem == 0) return 0;
        //有值则直接返回值，不重复计算
        if (count[rem - 1] != 0) return count[rem - 1];
        //枚举coin找到最小数量
        int Min = INT_MAX;
        for (int coin:coins) {
            int res = dp(coins, rem - coin);
            if (res >= 0 && res < Min) {//先排除-1
                Min = res + 1;
            }
        }
        count[rem - 1] = Min == INT_MAX ? -1 : Min;
        return count[rem - 1];
    }
public:
    int coinChange(vector<int>& coins, int amount) {
        if (amount < 1) return 0;//amount从1~S，不考虑0
        count.resize(amount);
        return dp(coins, amount);
    }
};

下面我们采用自下而上的方式进行思考。仍定义 F(i)F(i) 为组成金额 ii​​ 所需最少的硬币数量。则递推关系为：

F(i)=min⁡j=0,…,n−1F(i−Cj)+1F(i)=\min_{j=0,\dots,n-1} F(i-C_j)+1

当i=1i=1时，F(i)=0F(i)=0；当i<0i<0时，F(i)F(i)去掉。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int Max = amount + 1;
        vector<int> dp(amount + 1, Max);//初始化为amount+1
        dp[0] = 0;
        for (int i = 1; i <= amount; ++i) {
            for (int j = 0; j < (int)coins.size(); ++j) {
                if (coins[j] <= i) {//dp[负数]的情况去掉
                    dp[i] = min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
        //dp[amount] > amount说明没变化，还是初始值
    }
};

01背包和完全背包模板：

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}
Copyright ©star2dust RSS