代碼隨想錄算法訓練營|第五十九天|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++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中，如果使用类成员变量时未给定其初始值，那么它将被
阅读更多...
Java通过驱动包(jar包)连接MySQL数据库的步骤总结及验证方式

Java通过驱动包(jar包)连接MySQL数据库的步骤总结及验证方式

《Java通过驱动包(jar包)连接MySQL数据库的步骤总结及验证方式》本文详细介绍如何使用Java通过JDBC连接MySQL数据库,包括下载驱动、配置Eclipse环境、检测数据库连接等关键步骤,... 目录一、下载驱动包二、放jar包三、检测数据库连接JavaJava 如何使用 JDBC 连接 mys
阅读更多...
C++中NULL与nullptr的区别小结

C++中NULL与nullptr的区别小结

《C++中NULL与nullptr的区别小结》本文介绍了C++编程中NULL与nullptr的区别,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编... 目录C++98空值——NULLC++11空值——nullptr区别对比示例 C++98空值——NUL
阅读更多...
C++ Log4cpp跨平台日志库的使用小结

C++ Log4cpp跨平台日志库的使用小结

《C++Log4cpp跨平台日志库的使用小结》Log4cpp是c++类库,本文详细介绍了C++日志库log4cpp的使用方法,及设置日志输出格式和优先级,具有一定的参考价值,感兴趣的可以了解一下... 目录一、介绍1. log4cpp的日志方式2.设置日志输出的格式3. 设置日志的输出优先级二、Window
阅读更多...
一文详解SpringBoot中控制器的动态注册与卸载

一文详解SpringBoot中控制器的动态注册与卸载

《一文详解SpringBoot中控制器的动态注册与卸载》在项目开发中,通过动态注册和卸载控制器功能,可以根据业务场景和项目需要实现功能的动态增加、删除,提高系统的灵活性和可扩展性,下面我们就来看看Sp... 目录项目结构1. 创建 Spring Boot 启动类2. 创建一个测试控制器3. 创建动态控制器注
阅读更多...
Java中的雪花算法Snowflake解析与实践技巧

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.
阅读更多...
JavaSE正则表达式用法总结大全

JavaSE正则表达式用法总结大全

《JavaSE正则表达式用法总结大全》正则表达式就是由一些特定的字符组成,代表的是一个规则,：本文主要介绍JavaSE正则表达式用法的相关资料,文中通过代码介绍的非常详细,需要的朋友可以参考下... 目录常用的正则表达式匹配符正则表China编程达式常用的类Pattern类Matcher类PatternSynta
阅读更多...
从入门到精通C++11 ＜chrono＞ 库特性

从入门到精通C++11 ＜chrono＞ 库特性

《从入门到精通C++11＜chrono＞库特性》chrono库是C++11中一个非常强大和实用的库,它为时间处理提供了丰富的功能和类型安全的接口,通过本文的介绍,我们了解了chrono库的基本概念... 目录一、引言1.1 为什么需要<chrono>库1.2<chrono>库的基本概念二、时间段（Durat
阅读更多...
C++20管道运算符的实现示例

C++20管道运算符的实现示例

《C++20管道运算符的实现示例》本文简要介绍C++20管道运算符的使用与实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录标准库的管道运算符使用自己实现类似的管道运算符我们不打算介绍太多，因为它实际属于c++20最为重要的
阅读更多...
Visual Studio 2022 编译C++20代码的图文步骤

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性：
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2