代碼隨想錄算法訓練營|第五十九天|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。

相关文章

HarmonyOS学习(七)——UI（五）常用布局总结

HarmonyOS学习(七)——UI（五）常用布局总结

自适应布局 1.1、线性布局（LinearLayout） 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列，Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距，达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式，且在各类尺寸屏幕上表现一致，其中交叉轴为垂直时，取值为Vert
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
学习hash总结

学习hash总结

2014/1/29/   最近刚开始学hash，名字很陌生，但是hash的思想却很熟悉，以前早就做过此类的题，但是不知道这就是hash思想而已，说白了hash就是一个映射，往往灵活利用数组的下标来实现算法，hash的作用：1、判重；2、统计次数；
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
【C++ Primer Plus习题】13.4

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<
阅读更多...
第10章 中断和动态时钟显示

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始，按照书籍的划分，第10章开始就进入保护模式（Protected Mode）部分了，感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断（Interrupt）的设计，中断的几种方式：外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用： 为了更好的利用处理器的性能。协同快速和慢速设备一起工作
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
C++包装器

C++包装器

包装器 在 C++ 中，“包装器”通常指的是一种设计模式或编程技巧，用于封装其他代码或对象，使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍，可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型： 1. 函数包装器 函数包装器用于封装一个或多个函数，使其接口更统一或更便于调用。例如，std::function 是一个通用的函数包装器，它可以存储任意可调用对象（函数、函数
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页： 南桥几晴秋 🌈C++专栏： 南桥谈C++ 🌈C语言专栏： C语言学习系列 🌈Linux学习专栏： 南桥谈Linux 🌈数据结构学习专栏： 数据结构杂谈 🌈数据库学习专栏： 南桥谈MySQL 🌈Qt学习专栏： 南桥谈Qt 🌈菜鸡代码练习： 练习随想记录 🌈git学习： 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2