多種成都網(wǎng)站建設(shè)全網(wǎng)推廣外包公司
文章目錄
- 動(dòng)態(tài)規(guī)劃（子序列系列）
- 1. 最長(zhǎng)遞增子序列
- 2. 擺動(dòng)序列
- 3. 最長(zhǎng)遞增子序列的個(gè)數(shù)
- 4. 最長(zhǎng)數(shù)對(duì)鏈
- 5. 最長(zhǎng)定差子序列
- 6. 最長(zhǎng)的斐波那契子序列的長(zhǎng)度
- 7. 最長(zhǎng)等差數(shù)列
- 8. 等差數(shù)列劃分 || - 子序列
動(dòng)態(tài)規(guī)劃（子序列系列）
1. 最長(zhǎng)遞增子序列
題目鏈接
-
狀態(tài)表示
dp[i]表示到 i 位置時(shí)，所有子序列當(dāng)中最長(zhǎng)的子序列的長(zhǎng)度 -
狀態(tài)轉(zhuǎn)移方程
-
初始化
表中的所有數(shù)據(jù)初始化為1
-
填表
從左到右
-
返回值
返回整個(gè)dp表里面最大的值
AC代碼：
class Solution
{
public:int lengthOfLIS(vector<int>& nums) {int n = nums.size();vector<int> dp(n, 1);int ret = 1;for (int i = 1; i < n; i++){for (int j = 0; j < i; j++){if (nums[i] > nums[j]){dp[i] = max(dp[i], dp[j] + 1);}}ret = max(ret, dp[i]);}return ret;}
};
2. 擺動(dòng)序列
題目鏈接
-
狀態(tài)表示
f[i]表示：以 i 位置為結(jié)尾的所有子序列當(dāng)中，最后一個(gè)位置是上升的最長(zhǎng)擺動(dòng)序列的長(zhǎng)度g[i]表示：以 i 位置為結(jié)尾的所有子序列當(dāng)中，最后一個(gè)位置是下降的最長(zhǎng)擺動(dòng)序列的長(zhǎng)度 -
狀態(tài)轉(zhuǎn)移方程
-
初始化
表中的所有值初始化為1
-
填表
從左到右
-
返回值
返回兩個(gè)表中的最大值
AC代碼:
class Solution
{
public:int wiggleMaxLength(vector<int>& nums) {int n = nums.size();vector<int> f(n, 1), g(n, 1);int ret = 1;for (int i = 1; i < n; i++){for (int j = 0; j < i; j++){if (nums[i] > nums[j]) f[i] = max(f[i], g[j] + 1);else if (nums[i] < nums[j]) g[i] = max(g[i], f[j] + 1);}ret = max(ret, max(f[i], g[i]));}return ret;}
};
3. 最長(zhǎng)遞增子序列的個(gè)數(shù)
題目鏈接
這里需要用到一種思想：
如何一次遍歷數(shù)組，就可以找到最大數(shù)出現(xiàn)的次數(shù)
代碼實(shí)現(xiàn)：
#include <iostream>using namespace std;int main()
{int arr[] = {2, 3, 1, 234, 43, 342, 234, 5, 34, 43, 8, 342};int n = sizeof(arr)/sizeof(arr[0]);int maxval = 0;int count = 0;for (int i = 0; i < n; i++){if (arr[i] > maxval) maxval = arr[i], count = 1;else if (arr[i] == maxval) count++;}cout << maxval << endl;cout << count << endl;return 0;
}
-
狀態(tài)表示
len[i]表示以 i 位置為結(jié)尾所有子序列當(dāng)中，最長(zhǎng)遞增子序列的長(zhǎng)度count[i]表示以 i 位置為結(jié)尾所有子序列當(dāng)中，最長(zhǎng)遞增子序列的個(gè)數(shù) -
狀態(tài)轉(zhuǎn)移方程
-
初始化
所有值都初始化為1
-
填表
從左到右
-
返回值
count表最后一個(gè)
AC代碼：
class Solution
{
public:int findNumberOfLIS(vector<int>& nums) {int n = nums.size();vector<int> len(n, 1), count(n, 1);int retval = 1, retcount = 1;for (int i = 1; i < n; i++){for (int j = 0; j < i; j++){if (nums[i] > nums[j]){if (len[j] + 1 > len[i]) len[i] = len[j] + 1, count[i] = count[j];else if (len[j] + 1 == len[i]) count[i] += count[j];}}if (retval == len[i]) retcount += count[i];else if (retval < len[i]) retval = len[i], retcount = count[i];}return retcount;}
};
4. 最長(zhǎng)數(shù)對(duì)鏈
題目鏈接
分析：狀態(tài)表示以某個(gè)位置為結(jié)尾的時(shí)候，后面的元素不能影響當(dāng)前的填表，但是這個(gè)題目已經(jīng)影響打了，所有需要將數(shù)組排序
-
狀態(tài)表示
dp[i]表示以 i 位置為結(jié)尾的所有數(shù)對(duì)鏈當(dāng)中，最長(zhǎng)的數(shù)對(duì)鏈的長(zhǎng)度 -
狀態(tài)轉(zhuǎn)移方程
-
初始化
所有初始化為1
-
填表
從做到右
-
返回值
返回整個(gè)表的最大值
AC代碼：
class Solution
{
public:int findLongestChain(vector<vector<int>>& pairs) {sort(pairs.begin(), pairs.end());int n = pairs.size();vector<int> dp(n, 1);int ret = 1;for (int i = 1; i < n; i++){for (int j = 0; j < i; j++){if (pairs[i][0] > pairs[j][1]) {dp[i] = max(dp[i], dp[j] + 1);}}ret = max(ret, dp[i]);}return ret;}
};
5. 最長(zhǎng)定差子序列
題目鏈接
-
狀態(tài)表示
dp[i]表示到 i 位置時(shí)，所有的子序列當(dāng)中最長(zhǎng)的定差子序列的長(zhǎng)度 -
狀態(tài)轉(zhuǎn)移方程
-
初始化
將第一個(gè)元素對(duì)應(yīng)的dp值初始化為1
-
填表
從左到右
-
返回值
返回整個(gè)dp表里的最大值
AC代碼：
class Solution
{
public:int longestSubsequence(vector<int>& arr, int difference) {unordered_map<int, int> hash;hash[arr[0]] = 1;int ret = 1;for (int i = 1; i < arr.size(); i++){hash[arr[i]] = hash[arr[i] - difference] + 1;ret = max(ret, hash[arr[i]]);}return ret;}
};
6. 最長(zhǎng)的斐波那契子序列的長(zhǎng)度
題目鏈接
-
狀態(tài)表示
dp[i][j]表示以 i j 為結(jié)尾的所有子序列當(dāng)中，最長(zhǎng)的斐波那契數(shù)列的長(zhǎng)度 -
狀態(tài)轉(zhuǎn)移方程
優(yōu)化：將數(shù)組的元素和下標(biāo)綁定，方便查找
-
初始化
-
填表
-
返回值
返回值可能小于3， 這是應(yīng)該返回0
AC代碼：
class Solution
{
public:int lenLongestFibSubseq(vector<int>& arr) {int n = arr.size();unordered_map<int, int> hash;for (int i = 0; i < n; i++) hash[arr[i]] = i;vector<vector<int>> dp(n, vector<int>(n, 2));int ret = 2;for (int j = 2; j < n; j++) // 固定最后一個(gè)位置{for (int i = 1; i < j; i++){int a = arr[j] - arr[i];if (a < arr[i] && hash.count(a)){dp[i][j] = dp[hash[a]][i] + 1;}ret = max(ret, dp[i][j]);}}return ret < 3 ? 0 : ret;}
};
7. 最長(zhǎng)等差數(shù)列
題目鏈接
-
狀態(tài)表示
dp[i][j] 表示 以 i j 為結(jié)尾的所有子序列當(dāng)中最長(zhǎng)的等差子序列的長(zhǎng)度 -
狀態(tài)轉(zhuǎn)移方程
優(yōu)化：一邊dp一邊保存離它最近元素的下標(biāo)，當(dāng) i 位置填完之后將它填入哈希表中即可。所以需要先固定第倒數(shù)第二個(gè)元素，接著固定倒數(shù)第一個(gè)元素
-
初始化
-
填表
-
返回值
返回是整個(gè)dp表里的最大值
AC代碼：
class Solution
{
public:int longestArithSeqLength(vector<int>& nums) {unordered_map<int, int> hash;int n = nums.size();hash[nums[0]] = 0;vector<vector<int>> dp(n, vector<int>(n, 2));int ret = 2;for (int i = 1; i < n; i++){for (int j = i + 1; j < n; j++){int a = 2 * nums[i] - nums[j];if (hash.count(a)){dp[i][j] = dp[hash[a]][i] + 1;}ret = max(ret, dp[i][j]);}hash[nums[i]] = i;}return ret;}
};
8. 等差數(shù)列劃分 || - 子序列
題目鏈接
-
狀態(tài)表示
dp[i][j]表示以 i j 為是等差數(shù)列的子序列的個(gè)數(shù) -
狀態(tài)表示
-
初始化
-
填表
-
返回值
AC代碼：
class Solution
{
public:int numberOfArithmeticSlices(vector<int>& nums) {int n = nums.size();unordered_map<long long, vector<int>> hash;for (int i = 0; i < n; i++) hash[nums[i]].push_back(i);vector<vector<int>> dp(n, vector<int>(n));int sum = 0;for (int j = 2; j < n; j++) // 固定倒數(shù)第一個(gè){for (int i = 1; i < j; i++){long long a = (long long)nums[i] * 2 - nums[j];if (hash.count(a)){for (auto k : hash[a]){if (k < i) dp[i][j] += dp[k][i] + 1;else break;}}sum += dp[i][j];}}return sum;}
};