代碼隨想錄算法訓練營|第五十九天|647. 回文子串、7516.最长回文子序列、动态规划总结篇。刷题心得（c++）

2023-11-03 18:52
文章标签 算法 动态 规划 c++ 总结 最长 序列 回文 刷题 心得 子串 647 代碼 隨想錄 訓練營 第五十九 7516

本文主要是介绍代碼隨想錄算法訓練營|第五十九天|647. 回文子串、7516.最长回文子序列、动态规划总结篇。刷题心得（c++），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

讀題

647. 回文子串

看完代码随想录之后的想法

516.最长回文子序列

看完代码随想录之后的想法

647. 回文子串 - 實作

思路

動態規劃思路

雙指針思路

Code

動態規劃思路

雙指針思路

516.最长回文子序列 - 實作

思路

Code

动态规划 - 總結

動態規劃基礎

動態規劃五部曲

誤區

動態規劃與貪心算法的差別

靈魂三問

基礎題目

背包問題

背包問題 - 遞推公式

遍歷順序差異

打家劫舍

股票問題

子序列問題

編輯距離問題

回文子串問題

讀題

647. 回文子串

看完代码随想录之后的想法

對於dp數組的定義又有了進一步的了解，之前沒有想到可以使用i，j這兩個下標來表示範圍，理解過後使用上就比較知道怎做了，並且後續也有談到如何使用雙指針法進行，基本上就是利用回文子串的特性，相對的位置上一定相同，在這題上又加深了自己對於雙指針以及回文特性的操作。

516.最长回文子序列

看完代码随想录之后的想法

原本有想到應該是類似於647，但自己只有想清楚了下標，但沒有想清楚遞推公式，看題解之前並沒有去思考說相等等於原本的回文子串+2長度，並且不相等時當時想過很多，但後面看完之後才知道是去取兩段範圍內最長的部分，在這個題目當中又複習到了之前的操作。

 

647. 回文子串 - 實作

思路

動態規劃思路

<aside> 💡 根據字符串的性質決定dp數組的定義

</aside>

  1. 定義DP數組以及下標的含意

    dp[i][j]: [i, j]範圍內的字符串是否為回文子串

  2. 遞推公式

    dp[i][j] s[i] s[j] 相等有三種狀況

    1. 兩者指向同一個元素，範圍為0，j - i = 0;

    2. 兩者相差一個元素，即相鄰，範圍為1，j - i = 1;

    3. 兩者相差大於一個元素，其實可以想成兩者範圍內的元素是否為回文子串，如下圖

      如果[i+2, j-2] [i+1][j-1]都是回文子串，那當s[i]s[j]相等時，一定也會是回文子串

      |------|------|------|------|
i     i+1    i+2    j-1     jj-2

  3. 根據遞推公式、題意以及定義，確定DP數組如何初始化

    將dp數組都初始化為false，確保每一次的狀態都是由自己推的

  4. 確定遍歷順序

    可以看到dp[i][j]是由左下角的值推導出來的，所以遍歷順序應該是由下到上由左到右。

            +------------+------------+    |            |  dp[i][j]  |    +------------+------------+   |dp[i+1][j-1]|            |         +------------+------------+

雙指針思路

<aside> 💡 雙指針法，由中間往外擴散出去，進行遍歷

</aside>

  1. 定義函數，

    來遍歷以i，j為中心的數組，往左右擴散並確認是否為回文字串

    需要傳入的參數

    i，j，左邊界以及字串

    回傳以i、j為中心的的回文字串有多少個。

  2. 主函數

    有兩種狀況，i以及i與i+1，因為中心點有可能是一個數也有可能是兩個數

    遍歷字符串所有位置

    定義一個result變數紀錄回文字串的總數

Code

動態規劃思路

class Solution {
public:int countSubstrings(string s) {vector<vector<bool>> dp (s.size(), vector<bool>(s.size(), false));int result = 0;for(int i = s.size() - 1; i >= 0; i--) {for(int j = i; j < s.size(); j++) {if(s[i] == s[j]) {if(j - i <= 1) {dp[i][j] = true;result++;} else if(dp[i + 1][j - 1] == true) {dp[i][j] = true;result++;}}}}return result;}
};

雙指針思路

class Solution {
public:int countSubstrings(string s) {int result = 0;for(int i = 0; i < s.size(); i++) {result += extend(s, i, i, s.size());result += extend(s, i, i + 1, s.size());}return result;}int extend(string& s, int i, int j, int n) {int res = 0;while(i >= 0 && j < n && s[i] == s[j]) {i--;j++;res++;}return res;}
};

 

516.最长回文子序列 - 實作

思路

<aside> 💡 根據字符串的性質決定dp數組的定義

</aside>

  1. 定義DP數組以及下標的含意

    dp[i][j]: [i, j]範圍內的字符串最長回文子串長度為dp[i][j]

  2. 遞推公式

    相等: s[i] s[j] 相等代表說這兩個數值可以加入到回文子串最長的範圍內，所以是dp[i + 1][j - 1] + 2，代表上

    |------|------|------|------|
i     i+1    i+2    j-1     jj-2

    不相等: s[i] s[j] 不相等代表說這兩個數值無法到回文子串最長的範圍內，所以我們要找出上一次i ~ j - 1 以及i + 1 ~ j的這兩個範圍內，誰有最長的回文子串。

    所以是max(dp[i+1][j], dp[i][j - 1]) 範圍內哪段回文子串最長。

          
|--------------------|
i                   j-1|--------------------|i+1                   j
|------|------|------|------|
i     i+1    i+2    j-1     jj-2

    兩者指向同一個元素，範圍為0，j - i = 0;

    1. 兩者相差一個元素，即相鄰，範圍為1，j - i = 1;

    2. 兩者相差大於一個元素，其實可以想成兩者範圍內的元素是否為回文子串，如下圖

      如果[i+2, j-2] [i+1][j-1]都是回文子串，那當s[i]s[j]相等時，一定也會是回文子串

  3. 根據遞推公式、題意以及定義，確定DP數組如何初始化

    在i跟j 相同時，可以知道最長回文子串的長度都是1，而在遞推公式中是計算不到i、j相同的情況。

    將dp數組都初始化為0，並確保i、j相等的狀態都是1。

  4. 確定遍歷順序

    可以看到dp[i][j]是由左下角的值推導出來的，所以遍歷順序應該是由下到上由左到右。

            +------------+------------+    | dp[i][j-1] |  dp[i][j]  |    +------------+------------+   |dp[i+1][j-1]| dp[i+1][j] |         +------------+------------+

Code

class Solution {
public:int longestPalindromeSubseq(string s) {vector<vector<int>> dp (s.size(), vector<int>(s.size(), 0));for(int i = 0; i < s.size(); i++) dp[i][i] = 1;for(int i = s.size() - 1; i >= 0; i--) {for(int j = i + 1; j < s.size(); j++) {if(s[i] == s[j]) {dp[i][j] = dp[i + 1][j - 1] + 2;} else {dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);}}}return dp[0][s.size() - 1];}
};

 

动态规划 - 總結

動態規劃基礎

動態規劃五部曲

  1. 定義DP數組以及下標的含意

    如果想不清楚dp数组的具体含义，递归公式从何谈起，甚至初始化的时候就写错了。

    dp[i][j] i 代表甚麼意思，j代表甚麼意思

    dp[i] i 代表甚麼意思，元素代表甚麼意思

  2. 遞推公式

  3. 根據遞推公式，確定DP數組如何初始化

    例如**动态规划：不同路径还不够，要有障碍！ (opens new window)**在这道题目中，初始化才是重头戏

  4. 確定遍歷順序

    如果看过背包系列，特别是完全背包，那么两层for循环先后顺序绝对可以搞懵很多人，反而递归公式是简单的。

  5. 打印dp數組

    至于推导dp数组的重要性，动规专题里几乎每篇Carl都反复强调，当程序结果不对的时候，一定要自己推导公式，看看和程序打印的日志是否一样。

誤區

遞推公式不該是過於關注的點，它只是解題的一部分，別讓自己在解題時處於黑盒狀態

動態規劃與貪心算法的差別

動態規劃每一個狀態一定是由上一個狀態推導出來，而貪心則是從局部選最優堆疊成全局最優

靈魂三問

  • 这道题目我举例推导状态转移公式了么？
  • 我打印dp数组的日志了么？
  • 打印出来了dp数组和我想的一样么？

基礎題目

  • 动态规划：斐波那契数(opens new window)
  • 动态规划：爬楼梯(opens new window)
  • 动态规划：使用最小花费爬楼梯(opens new window)
  • 动态规划：不同路径(opens new window)
  • 动态规划：不同路径还不够，要有障碍！(opens new window)
  • 动态规划：整数拆分，你要怎么拆？(opens new window)
  • 动态规划：不同的二叉搜索树

背包問題

背包問題 - 遞推公式

  • 最多裝多少/能否裝滿

    dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); → 可以想像成物品重量與價值相等

    對應題目

    • 动态规划：416.分割等和子集(opens new window)
    • 动态规划：1049.最后一块石头的重量 II

  • 最大價值

    dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); → 可以想像成物品重量與價值不相等

    對應題目

    • 动态规划：474.一和零

  • 裝滿背包有多少方式

    dp[j] += dp[j - nums[i]];

    對應題目

    • 动态规划：494.目标和(opens new window)
    • 动态规划：518. 零钱兑换 II(opens new window)
    • 动态规划：377.组合总和Ⅳ(opens new window)
    • 动态规划：70. 爬楼梯进阶版（完全背包）

  • 最少裝多少/能否裝滿

    dp[j] = min(dp[j - coins[i]] + 1, dp[j])

    對應題目

    • 动态规划：322.零钱兑换(opens new window)
    • 动态规划：279.完全平方数

遍歷順序差異

  • 01背包

    • 二維dp

      因為數值都會根據左上方以及正上方的值進行更新，所以當我們初始化第一行與第一列時，不管是從背包開始遞推還是物品開始遞推，都可以。

      第二層遍歷順序是由小到大

    • 一維dp

      在二维數組中，每一層的數值都是當前位置的正上方以及左上方的數據得出

      從二维壓縮成一维數組，我們需要模擬二维數組的方式

      所以根據我們的遞推公式，我們不能使用正序遍歷，不然原本在二维數組中左上方的數據就會被覆蓋掉

      而使用倒序可以保證每一層的數據都是由二维數組上一層正上方以及左上方得出的。

    • 二維dp 滾動dp

      在**动态规划：474.一和零 中是有兩個維度的背包**

      先遍歷物品，在遍歷二維背包

      因為是滾動數組，所以二維背包是由後往前遍歷

  • 完全背包

    在純完全背包的問題當中，既然物品可以被選取無限次，那麼考慮某個物品時不必限制只看一次。

    換句話說，可以在考慮這個物品的同時也考慮其他所有的物品。

    因此，不論先遍歷物品還是先遍歷容量，結果都是一樣的。

    如果求最小数，那么两层for循环的先后顺序就无所谓了，相关题目如下：

    • 求最小数：动态规划：322. 零钱兑换 (opens new window)、动态规划：279.完全平方数

    但如果題目要求的回答是組合或者是排序就會有所差別

    組合 - 不要求順序性: 外層遍歷物品內層遍歷背包

    排列- 要求順序性: 外層遍歷背包內層遍歷物品

    相關題目

    • 求组合数：动态规划：518.零钱兑换II(opens new window)
    • 求排列数：动态规划：377. 组合总和 Ⅳ (opens new window)、动态规划：70. 爬楼梯进阶版（完全背包）

    可以想像在求組合的時候，外層遍歷物品，確保每個背包至多只會有一次的組合

    但在求排序時，因為每個背包都會重新遍歷物品，所以會有不同的順序被計算到

打家劫舍

  • 對應問題
    • 动态规划：开始打家劫舍！(opens new window)
    • 动态规划：继续打家劫舍！(opens new window)
    • 动态规划：还要打家劫舍！

股票問題

  • 單一股票買賣一次求最大数值，主要就是定義上持有股票的現金以及不持有的部分進行初步的劃分

    • 动态规划：121.买卖股票的最佳时机

    • 透過遞規公式找出数組中的最大数值

      dp[i][0] = max(dp[i - 1][0], -prices[i]);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);

  • 單一股票買賣多次求最大数值，主要就是定義上持有股票的現金以及不持有的部分進行初步的劃分

    • 动态规划：122.买卖股票的最佳时机II

    • 在遞推公式上就是在買入的時機會出現差異，變成是說上一次獲得的現金，減去當下的股票金額，哪個優

      dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]); 
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);

  • 單一股票只能買賣特定次数

    • 动态规划：123.买卖股票的最佳时机III 、 动态规划：188.买卖股票的最佳时机IV

    • 主要體現在下標上面就會有差異，分為沒有操作、買入股票、賣出股票這三個部分

    • 因為每次的買賣都一定是2 * k 次(買入、賣出)，所以在的推公式上其實就是將買賣次数進行抽象化處理

      for(int j = 1; j < 2 * k + 1; j++) {if(j % 2 == 1) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]);
}

  • 單一股票只能買賣包含冷凍期

    • 动态规划：309.最佳买卖股票时机含冷冻期

    • 主要體現在定義上會有所差別，需要將賣出的狀態分為，保持賣出以及賣出，這樣使得冷凍期的數值有所依歸

    • 遞推公式如下

      dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3]- prices[i], dp[i - 1][1]- prices[i]));
dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);
dp[i][2] = dp[i - 1][0] + prices[i];
dp[i][3] = dp[i - 1][2];

  • 單一股票多次買賣包含手續費

    • 动态规划：714.买卖股票的最佳时机含手续费

    • 主要體賣出時，需要多加上一個手續費的計算

    • 遞推公式如下

      dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]); 
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);

子序列問題

編輯距離問題

在編輯距離的題目當中，有個很重要的核心就是定義好dp[i][j]的定義，在根據這個定義，去推導出公式以及初始化的方式

其實前三題很重要的思維就是對於刪除的理解，在不同的定義上刪除的做法都不太一樣

  • 判斷子序列

刪除是dp[i][j - 1]，忽略前一個t

  • 不同子序列

使用s[i - 1]的，我不用刪除任何元素，所以值會是dp[i - 1][j - 1]即上一次的狀況，

如果不使用s[i - 1]的狀況，我等同於只需要不考慮s[i - 1] 但t[j - 1]仍然在，所以值會是dp[i - 1][j]

相同時的轉移方程就會是dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];

兩者不相等時相當於s 要刪除元素，因為 s的字符串中，這個位置並沒有t的字串，所以要刪除

如果是s要刪除元素，那就是取s[i - 2] 這個不包含s[ i -1]的最大值，但t是要比較的子序列，所以t不用動，也就是說這個dp[i][j]會是由s[i - 2]t[j - 1]所組成，所對應的dp數組是dp[i][j] = dp[i - 1][j]。

  • 兩個字符串的刪除操作

    • 刪除word1
      • 代表不包含當前word1的狀況在加上一個刪除的個數也就是dp[i - 1][j] + 1
    • 刪除word2
      • 代表不包含當前word2的狀況再加上1個刪除數，也就是dp[i][j - 1] + 1
    • 刪除word1、word2
      • 代表要不包含word1以及word2的值，也就是dp[i - 1][j - 1] ，並加上刪除兩次，所以是dp[i - 1][j - 1] + 2

  • 編輯距離

    所謂的增刪基本上是同一個操作數，只是需要明確甚麼是替換，以及下標定義為何

    • 需要增刪word1時，都是取dp[i - 1][j] + 1
    • 需要增刪word2時，都是取dp[i][j - 1] + 1
    • 需要替換word1或word2的話，則需要取這兩個都不存在的部分加上一次操作數也就是dp[i - 1][j - 1] + 1

  • 對應題目

    • 动态规划：最长递增子序列(opens new window)
    • 动态规划：最长连续递增序列(opens new window)
    • 动态规划：最长重复子数组(opens new window)
    • 动态规划：最长公共子序列(opens new window)
    • 动态规划：不相交的线(opens new window)
    • 动态规划：最大子序和(opens new window)
    • 动态规划：判断子序列(opens new window)
    • 动态规划：不同的子序列(opens new window)
    • 动态规划：两个字符串的删除操作(opens new window)
    • 动态规划：编辑距离

回文子串問題

<aside> 💡 根據字符串的性質決定dp數組的定義

</aside>

主要就是對於回文子串的性質要清晰，並且dp數組定義時要定義清楚

  • 對應題目
    • 动态规划：回文子串(opens new window)
    • 动态规划：最长回文子序列

这篇关于代碼隨想錄算法訓練營|第五十九天|647. 回文子串、7516.最长回文子序列、动态规划总结篇。刷题心得（c++）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/340201。

相关文章

C++中初始化二维数组的几种常见方法

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a
阅读更多...
openCV中KNN算法的实现

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库，它提供了各
阅读更多...
MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

《MySQL中动态生成SQL语句去掉所有字段的空格的操作方法》在数据库管理过程中,我们常常会遇到需要对表中字段进行清洗和整理的情况,本文将详细介绍如何在MySQL中动态生成SQL语句来去掉所有字段的空... 目录在mysql中动态生成SQL语句去掉所有字段的空格准备工作原理分析动态生成SQL语句在MySQL
阅读更多...
C++ vector的常见用法超详细讲解

C++ vector的常见用法超详细讲解

《C++vector的常见用法超详细讲解》：本文主要介绍C++vector的常见用法,包括C++中vector容器的定义、初始化方法、访问元素、常用函数及其时间复杂度,通过代码介绍的非常详细,... 目录1、vector的定义2、vector常用初始化方法1、使编程用花括号直接赋值2、使用圆括号赋值3、ve
阅读更多...
如何高效移除C++关联容器中的元素

如何高效移除C++关联容器中的元素

《如何高效移除C++关联容器中的元素》关联容器和顺序容器有着很大不同,关联容器中的元素是按照关键字来保存和访问的,而顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的,本文介绍了如何高效移除C+... 目录一、简介二、移除给定位置的元素三、移除与特定键值等价的元素四、移除满足特android定条件的元
阅读更多...
Python获取C++中返回的char*字段的两种思路

Python获取C++中返回的char*字段的两种思路

《Python获取C++中返回的char*字段的两种思路》有时候需要获取C++函数中返回来的不定长的char*字符串,本文小编为大家找到了两种解决问题的思路,感兴趣的小伙伴可以跟随小编一起学习一下... 有时候需要获取C++函数中返回来的不定长的char*字符串，目前我找到两种解决问题的思路，具体实现如下：
阅读更多...
C++ Sort函数使用场景分析

C++ Sort函数使用场景分析

《C++Sort函数使用场景分析》sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变,如果某些场景需要保持相同元素间的相对顺序,可使... 目录C++ Sort函数详解一、sort函数调用的两种方式二、sort函数使用场景三、sort函数排序
阅读更多...
Java调用C++动态库超详细步骤讲解(附源码)

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,：本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步：动态库生成（vs2017+qt5.12.10）第二步：Java调用C++
阅读更多...
springboot+dubbo实现时间轮算法

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n
阅读更多...
C/C++错误信息处理的常见方法及函数

C/C++错误信息处理的常见方法及函数

《C/C++错误信息处理的常见方法及函数》C/C++是两种广泛使用的编程语言,特别是在系统编程、嵌入式开发以及高性能计算领域,：本文主要介绍C/C++错误信息处理的常见方法及函数,文中通过代码介绍... 目录前言1. errno 和 perror()示例：2. strerror()示例：3. perror(
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2