【1027. 最长等差数列】
给你一个整数数组 nums，返回 nums 中最长等差子序列的长度。
回想一下，nums 的子序列是一个列表 nums[i1], nums[i2], ..., nums[ik] ，且 0 <= i1 < i2 < ... < ik <= nums.length - 1。并且如果 seq[i+1] - seq[i]( 0 <= i < seq.length - 1) 的值都相同，那么序列 seq 是等差的。
提示：
2 <= nums.length <= 1000
0 <= nums[i] <= 500
链接：https://leetcode.cn/problems/longest-arithmetic-subsequence/description/
使用二维dp数组来解决问题，因为每个元素的取值范围为[0,500]，因此公差可以取值的范围为[-500,500]，每个值均加500，可将范围平移得到[0,1000];
dp[i][d]的含义表示为以nums[i]为结尾的,公差为d+500的最长等差数列。
class Solution {public:int longestArithSeqLength(vector<int>& nums) {int n = nums.size();vector<vector<int>> rec(n, vector<int>(1001, 1));int res = 1;for (int i = 1; i < nums.size(); ++i) {for (int j = 0; j < i; ++j) {int d = nums[i] - nums[j] + 500;rec[i][d] = rec[j][d] + 1;res = max(rec[i][d], res);}}return res;}};
【276. 栅栏涂色】
有 k 种颜色的涂料和一个包含 n 个栅栏柱的栅栏，请你按下述规则为栅栏设计涂色方案：
每个栅栏柱可以用其中 一种 颜色进行上色。
相邻的栅栏柱 最多连续两个 颜色相同。
给你两个整数 k 和 n ，返回所有有效的涂色 方案数 。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/paint-fence/description/
class Solution {public:int numWays(int n, int k) {vector<vector<int>> rec(n, vector<int>(2));// rec[i][0]:与前一个栅栏涂相同的颜色// rec[i][1]:与前一个栅栏涂不同的颜色rec[0][1] = k;for (int i = 1; i < n; ++i) {rec[i][0] = rec[i - 1][1];rec[i][1] = (rec[i - 1][0] + rec[i - 1][1]) * (k - 1);}return rec[n - 1][0] + rec[n - 1][1];}};
【309. 最佳买卖股票时机含冷冻期】
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/
class Solution {public:int maxProfit(vector<int>& prices) {int n = prices.size();vector<vector<int>> f(n, vector<int>(3));// 第i天结束之后的收益，三种状态：// f[i][0]: 手上持有股票的最大收益// f[i][1]: 手上不持有股票，并且当天结束处于冷冻期中的累计最大收益// f[i][2]: 手上不持有股票，并且当天结束不在冷冻期中的累计最大收益f[0][0] = -prices[0];for (int i = 1; i < n; ++i) {f[i][0] = max(f[i - 1][0], f[i - 1][2] - prices[i]);f[i][1] = f[i - 1][0] + prices[i];f[i][2] = max(f[i - 1][1], f[i - 1][2]);}return max(f[n - 1][1], f[n - 1][2]);}};
【265. 粉刷房子 II】
假如有一排房子共有 n 幢，每个房子可以被粉刷成 k 种颜色中的一种。房子粉刷成不同颜色的花费成本也是不同的。你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
每个房子粉刷成不同颜色的花费以一个 n x k 的矩阵表示。
例如，costs[0][0] 表示第 0 幢房子粉刷成 0 号颜色的成本；costs[1][2] 表示第 1 幢房子粉刷成 2 号颜色的成本，以此类推。
返回 粉刷完所有房子的最低成本 。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/paint-house-ii/description
class Solution {public:int minCostII(vector<vector<int>>& costs) {int n = costs.size();int types = costs[0].size();int res = INT_MAX;vector<vector<int>> rec(n, vector<int>(types, INT_MAX));for (int i = 0; i < types; ++i) {rec[0][i] = costs[0][i];}for (int i = 1; i < n; ++i) {for (int j = 0; j < types; ++j) {for (int t = 1; t < types; ++t) {rec[i][j] = min(rec[i - 1][(j + t) % types], rec[i][j]);}rec[i][j] += costs[i][j];}}for (int i = 0; i < types; ++i) {res = min(rec[n - 1][i], res);}return res;}};
相关推荐：
