深圳幻海软件技术有限公司 欢迎您！
更多

力扣 C++｜一题多解之动态规划专题（2）

2023-09-05

int cout endl
动态规划DynamicProgramming简写为DP，是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军

动态规划

Dynamic Programming

简写为 DP，是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。

动态规划算法的基本步骤包括：

  1. 确定状态：确定需要求解的状态，并将其表示为变量。
  2. 确定状态转移方程：根据问题的特定约束条件和目标函数，确定状态之间的转移关系，并将其表示为数学公式。
  3. 初始化：为初始状态赋初值，并将其表示为初始条件。
  4. 递推计算：根据状态转移方程，使用循环依次计算各个状态的解，并将其保存在数组或表中。
  5. 求解最终结果：根据问题的目标，从计算得到的解中得出最终结果。

动态规划算法可以用于解决各种问题，例如最短路径问题、背包问题、最长公共子序列问题等。在实现动态规划算法时，需要根据具体问题的特点进行设计和调整，以确保算法的正确性和效率。

适用条件

任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。

最优化原理（最优子结构性质）

最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质 [8] 。

无后效性

将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性 [8] 。

子问题的重叠性

动态规划算法的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其他的算法。选择动态规划算法是因为动态规划算法在空间上可以承受，而搜索算法在时间上却无法承受，所以我们舍空间而取时间。

真题举例（2）

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
        1.  1 阶 + 1 阶
        2.  2 阶

示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
        1.  1 阶 + 1 阶 + 1 阶
        2.  1 阶 + 2 阶
        3.  2 阶 + 1 阶

代码1： 

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Solution
  5. {
  6. public:
  7.     int climbStairs(int n)
  8.     {
  9.         if (n == 1)
  10.         {
  11.             return 1;
  12.         }
  13.         int first = 1;
  14.         int second = 2;
  15.         for (int i = 3; i <= n; i++)
  16.         {
  17.             int third = first + second;
  18.             first = second;
  19.             second = third;
  20.         }
  21.         return second;
  22.     }
  23. };
  24.  
  25. int main()
  26. {
  27. Solution s;
  28.  
  29. cout << s.climbStairs(2) << endl;
  30. cout << s.climbStairs(3) << endl;
  32. return 0;
  33. }

代码2：  

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Solution
  5. {
  6. public:
  7.     int climbStairs(int n)
  8.     {
  9.         vector<int> res(n + 1, 0);
  10.         res[1] = 1;
  11.         res[2] = 2;
  12.         for (int i = 3; i <= n; i++)
  13.             res[i] = res[i - 1] + res[i - 2];
  14.         return res[n];
  15.     }
  16. };
  17.  
  18. int main()
  19. {
  20. Solution s;
  21.  
  22. cout << s.climbStairs(2) << endl;
  23. cout << s.climbStairs(3) << endl;
  25. return 0;
  26. }

代码3：  

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Solution
  5. {
  6. public:
  7.     int climbStairs(int n)
  8.     {
  9.         vector<int> s;
  10.         s.push_back(1);
  11.         s.push_back(2);
  12.         if (n == 1)
  13.             return 1;
  14.         if (n == 2)
  15.             return 2;
  16.         for (int i = 2; i < n; i++)
  17.         {
  18.             s.push_back(s[i - 1] + s[i - 2]);
  19.         }
  20.         return s[n - 1];
  21.     }
  22. };
  23.  
  24. int main()
  25. {
  26. Solution s;
  27.  
  28. cout << s.climbStairs(2) << endl;
  29. cout << s.climbStairs(3) << endl;
  31. return 0;
  32. }

72. 编辑距离

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：horse -> rorse (将 'h' 替换为 'r')rorse -> rose (删除 'r')rose -> ros (删除 'e')

示例 2：

输入：word1 = "intention", word2 = "execution"
输出：5
解释：intention -> inention (删除 't')inention -> enention (将 'i' 替换为 'e')enention -> exention (将 'n' 替换为 'x')exention -> exection (将 'n' 替换为 'c')exection -> execution (插入 'u')

提示：

  • 0 <= word1.length, word2.length <= 500
  • word1 和 word2 由小写英文字母组成

代码1：  

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Solution
  5. {
  6. public:
  7.     int minDistance(string word1, string word2)
  8.     {
  9.         int m = word1.size(), n = word2.size();
  10.  
  11.         if (m == 0)
  12.             return n;
  13.         if (n == 0)
  14.             return m;
  15.  
  16.         int dp[m][n];
  17.         bool w1 = false, w2 = false;
  18.         if (word1[0] == word2[0])
  19.         {
  20.             w1 = true;
  21.             w2 = true;
  22.             dp[0][0] = 0;
  23.         }
  24.         else
  25.             dp[0][0] = 1;
  26.         for (int i = 1; i < m; i++)
  27.         {
  28.             if (!w1 && word1[i] == word2[0])
  29.             {
  30.                 w1 = true;
  31.                 dp[i][0] = dp[i - 1][0];
  32.             }
  33.             else
  34.                 dp[i][0] = dp[i - 1][0] + 1;
  35.         }
  36.         for (int j = 1; j < n; j++)
  37.         {
  38.             if (!w2 && word1[0] == word2[j])
  39.             {
  40.                 w2 = true;
  41.                 dp[0][j] = dp[0][j - 1];
  42.             }
  43.             else
  44.                 dp[0][j] = dp[0][j - 1] + 1;
  45.         }
  46.  
  47.         for (int i = 1; i < m; i++)
  48.             for (int j = 1; j < n; j++)
  49.                 if (word1[i] == word2[j])
  50.                     dp[i][j] = min(min(dp[i][j - 1], dp[i - 1][j]) + 1, dp[i - 1][j - 1]);
  51.                 else
  52.                     dp[i][j] = min(min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
  53.         return dp[m - 1][n - 1];
  54.     }
  55. };
  56.  
  57. int main()
  58. {
  59. Solution s;
  60. string word1 = "horse", word2 = "ros";
  61. cout << s.minDistance(word1, word2) << endl;
  63. word1 = "intention", word2 = "execution";
  64. cout << s.minDistance(word1, word2) << endl;
  66. return 0;
  67. }

代码2：  

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Solution
  5. {
  6. public:
  7.     int minDistance(string word1, string word2)
  8.     {
  9.         int n = word1.size();
  10.         int m = word2.size();
  11.  
  12.         if (n * m == 0)
  13.         {
  14.             return n + m;
  15.         }
  16.  
  17.         int d[n + 1][m + 1];
  18.         for (int i = 0; i < n + 1; ++i)
  19.         {
  20.             d[i][0] = i;
  21.         }
  22.         for (int i = 0; i < m + 1; ++i)
  23.         {
  24.             d[0][i] = i;
  25.         }
  26.  
  27.         for (int i = 1; i < n + 1; ++i)
  28.         {
  29.             for (int j = 1; j < m + 1; ++j)
  30.             {
  31.                 int left = d[i - 1][j] + 1;
  32.                 int down = d[i][j - 1] + 1;
  33.                 int left_down = d[i - 1][j - 1];
  34.                 if (word1[i - 1] != word2[j - 1])
  35.                 {
  36.                     left_down += 1;
  37.                 }
  38.                 d[i][j] = min(left, min(down, left_down));
  39.             }
  40.         }
  41.         return d[n][m];
  42.     }
  43. };
  44.  
  45. int main()
  46. {
  47. Solution s;
  48. string word1 = "horse", word2 = "ros";
  49. cout << s.minDistance(word1, word2) << endl;
  51. word1 = "intention", word2 = "execution";
  52. cout << s.minDistance(word1, word2) << endl;
  54. return 0;
  55. }

代码3：  

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Solution
  5. {
  6. public:
  7.     int minDistance(string word1, string word2)
  8.     {
  9.         int m = word1.size(), n = word2.size();
  10.  
  11.         vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
  12.  
  13.         for (int i = 1; i <= n; ++i)
  14.             dp[0][i] = dp[0][i - 1] + 1;
  15.         for (int i = 1; i <= m; ++i)
  16.             dp[i][0] = dp[i - 1][0] + 1;
  17.  
  18.         for (int i = 1; i <= m; ++i)
  19.         {
  20.             for (int j = 1; j <= n; ++j)
  21.             {
  22.                 if (word1[i - 1] == word2[j - 1])
  23.                     dp[i][j] = dp[i - 1][j - 1];
  24.                 else
  25.                     dp[i][j] = min(min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) + 1;
  26.             }
  27.         }
  28.         return dp[m][n];
  29.     }
  30. };
  31.  
  32. int main()
  33. {
  34. Solution s;
  35. string word1 = "horse", word2 = "ros";
  36. cout << s.minDistance(word1, word2) << endl;
  38. word1 = "intention", word2 = "execution";
  39. cout << s.minDistance(word1, word2) << endl;
  41. return 0;
  42. }

代码4：  

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Solution {
  5. public:
  6.     int minDistance(string word1, string word2) {
  7.         int len1 = word1.size();
  8.         int len2 = word2.size();
  9.         int **dp = new int *[len1 + 1];
  10.         for (int i = 0; i < len1 + 1; i++)
  11.             dp[i] = new int[len2 + 1];
  12.         for (int i = 0; i < len1 + 1; i++)
  13.             dp[i][0] = i;
  14.         for (int i = 0; i < len2 + 1; i++)
  15.             dp[0][i] = i;
  16.         for (int i = 1; i < len1 + 1; i++) {
  17.             for (int j = 1; j < len2 + 1; j++) {
  18.                 if (word1[i - 1] == word2[j - 1])
  19.                     dp[i][j] = dp[i - 1][j - 1];
  20.                 else
  21.                     dp[i][j] = (min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1);
  22.             }
  23.         }
  24.         int res = dp[len1][len2];
  25.         for (int i = 0; i < len1 + 1; i++)
  26.             delete[] dp[i];
  27.         delete[] dp;
  28.         return res;
  29.     }
  30. };
  31.  
  32. int main()
  33. {
  34. Solution s;
  35. string word1 = "horse", word2 = "ros";
  36. cout << s.minDistance(word1, word2) << endl;
  38. word1 = "intention", word2 = "execution";
  39. cout << s.minDistance(word1, word2) << endl;
  41. return 0;
  42. }

85. 最大矩形

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例 1：

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6
解释：最大矩形如上图所示。

示例 2：

输入：matrix = []
输出：0

示例 3：

输入：matrix = [["0"]]
输出：0

示例 4：

输入：matrix = [["1"]]
输出：1

示例 5：

输入：matrix = [["0","0"]]
输出：0

提示：

  • rows == matrix.length
  • cols == matrix[0].length
  • 0 <= row, cols <= 200
  • matrix[i][j] 为 '0' 或 '1'

代码1： 

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Solution
  5. {
  6. public:
  7.     int maximalRectangle(vector<vector<char>> &matrix)
  8.     {
  9.         if (matrix.size() == 0)
  10.         {
  11.             return 0;
  12.         }
  13.         int maxarea = 0;
  14.         int dp[matrix.size()][matrix[0].size()];
  15.         memset(dp, 0, sizeof(dp));
  16.  
  17.         for (int i = 0; i < matrix.size(); ++i)
  18.         {
  19.             for (int j = 0; j < matrix[0].size(); ++j)
  20.             {
  21.                 if (matrix[i][j] == '1')
  22.                 {
  23.                     dp[i][j] = j == 0 ? 1 : dp[i][j - 1] + 1;
  24.                     int width = dp[i][j];
  25.  
  26.                     for (int k = i; k >= 0; k--)
  27.                     {
  28.                         width = min(width, dp[k][j]);
  29.                         maxarea = max(maxarea, width * (i - k + 1));
  30.                     }
  31.                 }
  32.             }
  33.         }
  34.         return maxarea;
  35.     }
  36. };
  37.  
  38. int main()
  39. {
  40. Solution s;
  41. vector<vector<char>> matrix = {
  42. {'1','0','1','0','0'},
  43. {'1','0','1','1','1'},
  44. {'1','1','1','1','1'},
  45. {'1','0','0','1','0'}};
  46. cout << s.maximalRectangle(matrix) << endl;
  48. matrix = {};
  49. cout << s.maximalRectangle(matrix) << endl;
  51. matrix = {{'0'}};
  52. cout << s.maximalRectangle(matrix) << endl;
  54. matrix = {{'1'}};
  55. cout << s.maximalRectangle(matrix) << endl;
  57. matrix = {{'0','0'}};
  58. cout << s.maximalRectangle(matrix) << endl;
  60. return 0;
  61. }

代码2：  

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Solution
  5. {
  6. public:
  7.     int maximalRectangle(vector<vector<char>> &matrix)
  8.     {
  9.         int res = 0;
  10.         vector<int> height;
  11.         for (int i = 0; i < matrix.size(); ++i)
  12.         {
  13.             height.resize(matrix[i].size());
  14.             for (int j = 0; j < matrix[i].size(); ++j)
  15.             {
  16.                 height[j] = matrix[i][j] == '0' ? 0 : (1 + height[j]);
  17.             }
  18.             res = max(res, largestRectangleArea(height));
  19.         }
  20.         return res;
  21.     }
  22.  
  23.     int largestRectangleArea(vector<int> &heights)
  24.     {
  25.         if (heights.empty())
  26.             return 0;
  27.         stack<int> st;
  28.         heights.push_back(0);
  29.         int res0 = 0;
  30.         for (int i = 0; i < heights.size(); i++)
  31.         {
  32.             while (!st.empty() && heights[i] < heights[st.top()])
  33.             {
  34.                 int curHeight = heights[st.top()];
  35.                 st.pop();
  36.                 int width = st.empty() ? i : i - st.top() - 1;
  37.                 if (width * curHeight > res0)
  38.                     res0 = width * curHeight;
  39.             }
  40.             st.push(i);
  41.         }
  42.         return res0;
  43.     }
  44. };
  45.  
  46. int main()
  47. {
  48. Solution s;
  49. vector<vector<char>> matrix = {
  50. {'1','0','1','0','0'},
  51. {'1','0','1','1','1'},
  52. {'1','1','1','1','1'},
  53. {'1','0','0','1','0'}};
  54. cout << s.maximalRectangle(matrix) << endl;
  56. matrix = {};
  57. cout << s.maximalRectangle(matrix) << endl;
  59. matrix = {{'0'}};
  60. cout << s.maximalRectangle(matrix) << endl;
  62. matrix = {{'1'}};
  63. cout << s.maximalRectangle(matrix) << endl;
  65. matrix = {{'0','0'}};
  66. cout << s.maximalRectangle(matrix) << endl;
  68. return 0;
  69. }

代码3：  

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Solution
  5. {
  6. public:
  7.     int largestRectangleArea(vector<int> &heights)
  8.     {
  9.         stack<int> h;
  10.         heights.push_back(0);
  11.         int ans = 0, hsize = heights.size();
  12.         for (int i = 0; i < hsize; i++)
  13.         {
  14.             while (!h.empty() && heights[h.top()] > heights[i])
  15.             {
  16.                 int top = h.top();
  17.                 h.pop();
  18.                 ans = max(ans, heights[top] * (h.empty() ? i : (i - h.top())));
  19.             }
  20.             h.push(i);
  21.         }
  22.         return ans;
  23.     }
  24.  
  25.     int maximalRectangle(vector<vector<char>> &matrix)
  26.     {
  27.         if (matrix.empty())
  28.             return 0;
  29.         int n = matrix.size(), m = matrix[0].size(), ans = 0;
  30.         vector<vector<int>> num(n, vector<int>(m, 0));
  31.         for (int j = 0; j < m; j++)
  32.         {
  33.             num[0][j] = (matrix[0][j] == '0') ? 0 : 1;
  34.             for (int i = 1; i < n; i++)
  35.                 num[i][j] = (matrix[i][j] == '0') ? 0 : num[i - 1][j] + 1;
  36.         }
  37.         for (int i = 0; i < n; i++)
  38.         {
  39.             int area = largestRectangleArea(num[i]);
  40.             ans = max(ans, area);
  41.         }
  42.         return ans;
  43.     }
  44. };
  45.  
  46. int main()
  47. {
  48. Solution s;
  49. vector<vector<char>> matrix = {
  50. {'1','0','1','0','0'},
  51. {'1','0','1','1','1'},
  52. {'1','1','1','1','1'},
  53. {'1','0','0','1','0'}};
  54. cout << s.maximalRectangle(matrix) << endl;
  56. matrix = {};
  57. cout << s.maximalRectangle(matrix) << endl;
  59. matrix = {{'0'}};
  60. cout << s.maximalRectangle(matrix) << endl;
  62. matrix = {{'1'}};
  63. cout << s.maximalRectangle(matrix) << endl;
  65. matrix = {{'0','0'}};
  66. cout << s.maximalRectangle(matrix) << endl;
  68. return 0;
  69. }

87. 扰乱字符串

使用下面描述的算法可以扰乱字符串 s 得到字符串 t ：

  1. 如果字符串的长度为 1 ，算法停止
  2. 如果字符串的长度 > 1 ，执行下述步骤：
    • 在一个随机下标处将字符串分割成两个非空的子字符串。即，如果已知字符串 s ，则可以将其分成两个子字符串 x 和 y ，且满足 s = x + y 。
    • 随机 决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不变」。即，在执行这一步骤之后，s 可能是 s = x + y 或者 s = y + x 。
    • 在 x 和 y 这两个子字符串上继续从步骤 1 开始递归执行此算法。

给你两个 长度相等 的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：s1 = "great", s2 = "rgeat"

输出：true
解释：s1 上可能发生的一种情形是：
"great" --> "gr/eat" // 在一个随机下标处分割得到两个子字符串
"gr/eat" --> "gr/eat" // 随机决定：「保持这两个子字符串的顺序不变」
"gr/eat" --> "g/r / e/at" // 在子字符串上递归执行此算法。两个子字符串分别在随机下标处进行一轮分割
"g/r / e/at" --> "r/g / e/at" // 随机决定：第一组「交换两个子字符串」，第二组「保持这两个子字符串的顺序不变」
"r/g / e/at" --> "r/g / e/ a/t" // 继续递归执行此算法，将 "at" 分割得到 "a/t"
"r/g / e/ a/t" --> "r/g / e/ a/t" // 随机决定：「保持这两个子字符串的顺序不变」
算法终止，结果字符串和 s2 相同，都是 "rgeat"
这是一种能够扰乱 s1 得到 s2 的情形，可以认为 s2 是 s1 的扰乱字符串，返回 true

示例 2：

输入：s1 = "abcde", s2 = "caebd"
输出：false

示例 3：

输入：s1 = "a", s2 = "a"
输出：true

提示：

  • s1.length == s2.length
  • 1 <= s1.length <= 30
  • s1 和 s2 由小写英文字母组成

代码1：  

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Solution
  5. {
  6. public:
  7.     bool isScramble(string s1, string s2)
  8.     {
  9.  
  10.         if (s1.size() != s2.size())
  11.             return false;
  12.         if (s1 == s2)
  13.             return true;
  14.         vector<int> hash(26, 0);
  15.  
  16.         for (int i = 0; i < s1.size(); i++)
  17.             hash.at(s1[i] - 'a')++;
  18.  
  19.         for (int j = 0; j < s2.size(); j++)
  20.             hash.at(s2[j] - 'a')--;
  21.  
  22.         for (int k = 0; k < 26; k++)
  23.         {
  24.             if (hash.at(k) != 0)
  25.                 return false;
  26.         }
  27.  
  28.         for (int i = 1; i < s1.size(); i++)
  29.         {
  30.             if (
  31.                 (isScramble(s1.substr(0, i), s2.substr(0, i)) && isScramble(s1.substr(i, s1.size() - i), s2.substr(i, s1.size() - i))) || (isScramble(s1.substr(0, i), s2.substr(s1.size() - i)) && isScramble(s1.substr(i), s2.substr(0, s1.size() - i))))
  32.                 return true;
  33.         }
  34.         return false;
  35.     }
  36. };
  37.  
  38. int main()
  39. {
  40. Solution s;
  41. cout << s.isScramble("great", "rgeat") << endl;
  42. cout << s.isScramble("abcde", "caebd") << endl;
  43. cout << s.isScramble("a", "a") << endl;
  45. return 0;
  46. }

代码2：  

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Solution
  5. {
  6. public:
  7.     bool isScramble(string s1, string s2)
  8.     {
  9.         int n1 = s1.length(), n2 = s2.length();
  10.         if (n1 != n2)
  11.             return false;
  12.         vector<vector<vector<bool>>> dp(n1 + 1, vector<vector<bool>>(n1 + 1, vector<bool>(n1 + 1, false)));
  13.         int i, j, k;
  14.         for (i = 1; i <= n1; i++)
  15.         {
  16.             for (j = 1; j <= n1; j++)
  17.             {
  18.                 dp[i][j][1] = (s1[i - 1] == s2[j - 1]);
  19.             }
  20.         }
  21.         for (int len = 2; len <= n1; len++)
  22.         {
  23.             for (i = 1; i <= n1 && i + len <= n1 + 1; i++)
  24.             {
  25.                 for (j = 1; j <= n1 && j + len <= n1 + 1; j++)
  26.                 {
  27.                     for (k = 1; k < len; k++)
  28.                     {
  29.                         if (dp[i][j][k] && dp[i + k][j + k][len - k])
  30.                         {
  31.                             dp[i][j][len] = true;
  32.                             break;
  33.                         }
  34.                         if (dp[i][j + len - k][k] && dp[i + k][j][len - k])
  35.                         {
  36.                             dp[i][j][len] = true;
  37.                             break;
  38.                         }
  39.                     }
  40.                 }
  41.             }
  42.         }
  43.  
  44.         return dp[1][1][n1];
  45.     }
  46. };
  47.  
  48. int main()
  49. {
  50. Solution s;
  51. cout << s.isScramble("great", "rgeat") << endl;
  52. cout << s.isScramble("abcde", "caebd") << endl;
  53. cout << s.isScramble("a", "a") << endl;
  55. return 0;
  56. }

代码3：  

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Solution
  5. {
  6. public:
  7.     bool isScramble(string s1, string s2)
  8.     {
  9.         if (s1.size() != s2.size())
  10.             return false;
  11.         if (s1 == s2)
  12.             return true;
  13.         string str1 = s1, str2 = s2;
  14.         sort(str1.begin(), str1.end());
  15.         sort(str2.begin(), str2.end());
  16.         if (str1 != str2)
  17.             return false;
  18.         for (int i = 1; i < s1.size(); ++i)
  19.         {
  20.             string s11 = s1.substr(0, i);
  21.             string s12 = s1.substr(i);
  22.             string s21 = s2.substr(0, i);
  23.             string s22 = s2.substr(i);
  24.             if (isScramble(s11, s21) && isScramble(s12, s22))
  25.                 return true;
  26.             s21 = s2.substr(s2.size() - i);
  27.             s22 = s2.substr(0, s2.size() - i);
  28.             if (isScramble(s11, s21) && isScramble(s12, s22))
  29.                 return true;
  30.         }
  31.         return false;
  32.     }
  33. };
  34.  
  35. int main()
  36. {
  37. Solution s;
  38. cout << s.isScramble("great", "rgeat") << endl;
  39. cout << s.isScramble("abcde", "caebd") << endl;
  40. cout << s.isScramble("a", "a") << endl;
  42. return 0;
  43. }

91. 解码方法

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

'A' -> 1'B' -> 2...'Z' -> 26

要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：

  • "AAJF" ，将消息分组为 (1 1 10 6)
  • "KJF" ，将消息分组为 (11 10 6)

注意，消息不能分组为  (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。

给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。

题目数据保证答案肯定是一个 32 位 的整数。

示例 1：

输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2：

输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

示例 3：

输入：s = "0"
输出：0
解释：没有字符映射到以 0 开头的数字。含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。

示例 4：

输入：s = "06"
输出：0
解释："06" 不能映射到 "F" ，因为字符串含有前导 0（"6" 和 "06" 在映射中并不等价）。

提示：

  • 1 <= s.length <= 100
  • s 只包含数字，并且可能包含前导零。

代码1： 

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Solution
  5. {
  6. public:
  7.     int numDecodings(string s)
  8.     {
  9.         vector<int> nums(s.size());
  10.         if (s[0] == '0')
  11.         {
  12.             return 0;
  13.         }
  14.         nums[0] = 1;
  15.  
  16.         if (s.size() > 1)
  17.         {
  18.             if (s[1] != '0')
  19.             {
  20.                 nums[1] += 1;
  21.             }
  22.             if ((s[0] - '0') * 10 + (s[1] - '0') <= 26)
  23.             {
  24.                 nums[1] += 1;
  25.             }
  26.         }
  27.  
  28.         for (int i = 2; i < s.size(); i++)
  29.         {
  30.             if (s[i] != '0')
  31.             {
  32.                 nums[i] += nums[i - 1];
  33.             }
  34.             if (s[i - 1] != '0' && ((s[i - 1] - '0') * 10 + (s[i] - '0') <= 26))
  35.             {
  36.                 nums[i] += nums[i - 2];
  37.             }
  38.         }
  39.         return nums[s.size() - 1];
  40.     }
  41. };
  42.  
  43. int main()
  44. {
  45. Solution s;
  46. cout << s.numDecodings("12") << endl;
  47. cout << s.numDecodings("226") << endl;
  48. cout << s.numDecodings("0") << endl;
  49. cout << s.numDecodings("06") << endl;
  51. return 0;
  52. }

代码2：  

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Solution
  5. {
  6. public:
  7.     int numDecodings(string s)
  8.     {
  9.         int n = s.size();
  10.         if (s.empty())
  11.             return 0;
  12.         if (s[0] == '0')
  13.             return 0;
  14.         vector<int> info(n + 1, 0);
  15.         info[0] = 1;
  16.         info[1] = 1;
  17.         for (int i = 2; i < n + 1; ++i)
  18.         {
  19.             if (s[i - 1] != '0')
  20.                 info[i] += info[i - 1];
  21.             if (s.substr(i - 2, 2) <= "26" && s.substr(i - 2, 2) >= "10")
  22.                 info[i] += info[i - 2];
  23.         }
  24.         return info[n];
  25.     }
  26. };
  27.  
  28. int main()
  29. {
  30. Solution s;
  31. cout << s.numDecodings("12") << endl;
  32. cout << s.numDecodings("226") << endl;
  33. cout << s.numDecodings("0") << endl;
  34. cout << s.numDecodings("06") << endl;
  36. return 0;
  37. }

代码3：  

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Solution
  5. {
  6. public:
  7.     int dp(string &s, int i, int j)
  8.     {
  9.         int n = j - i + 1;
  10.         if (n == 0)
  11.             return 0;
  12.         if (n == 1)
  13.             return s[i] == '0' ? 0 : 1;
  14.         if (n == 2)
  15.         {
  16.             if (s[i] == '0')
  17.                 return 0;
  18.             if (s[i] > '2')
  19.                 return s[j] == '0' ? 0 : 1;
  20.             if (s[i] == '2' && s[j] > '6')
  21.                 return 1;
  22.             if (s[j] == '0')
  23.                 return 1;
  24.             return 2;
  25.         }
  26.         if (s[i] > '2')
  27.             return dp(s, i + 1, j);
  28.         if (s[i] == '2')
  29.         {
  30.             if (s[i + 1] == '0')
  31.                 return dp(s, i + 2, j);
  32.             else if (s[i + 1] < '7')
  33.                 return dp(s, i + 1, j) + dp(s, i + 2, j);
  34.             else
  35.                 return dp(s, i + 1, j);
  36.         }
  37.         if (s[i] == '0')
  38.             return 0;
  39.         if (s[i + 1] == '0')
  40.             return dp(s, i + 2, j);
  41.         return dp(s, i + 1, j) + dp(s, i + 2, j);
  42.     }
  43.     int numDecodings(string s)
  44.     {
  45.         return dp(s, 0, s.size() - 1);
  46.     }
  47. };
  48.  
  49. int main()
  50. {
  51. Solution s;
  52. cout << s.numDecodings("12") << endl;
  53. cout << s.numDecodings("226") << endl;
  54. cout << s.numDecodings("0") << endl;
  55. cout << s.numDecodings("06") << endl;
  57. return 0;
  58. }

代码4：  

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Solution {
  5. public:
  6.     int numDecodings(string s) {
  7.         int n = s.size();
  8.         vector<int> f(n + 1);
  9.         f[0] = 1;
  10.         for (int i = 1; i <= n; ++i) {
  11.             if (s[i - 1] != '0') {
  12.                 f[i] += f[i - 1];
  13.             }
  14.             if (i > 1 && s[i - 2] != '0' && ((s[i - 2] - '0') * 10 + (s[i - 1] - '0') <= 26)) {
  15.                 f[i] += f[i - 2];
  16.             }
  17.         }
  18.         return f[n];
  19.     }
  20. };
  21.  
  22. int main()
  23. {
  24. Solution s;
  25. cout << s.numDecodings("12") << endl;
  26. cout << s.numDecodings("226") << endl;
  27. cout << s.numDecodings("0") << endl;
  28. cout << s.numDecodings("06") << endl;
  30. return 0;
  31. }

代码5：  

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Solution
  5. {
  6. public:
  7.     int numDecodings(string s)
  8.     {
  9.         if (s.empty() || s[0] == '0')
  10.             return 0;
  11.         vector<int> dp(s.size() + 1, 0);
  12.         dp[0] = 1;
  13.         for (int i = 1; i < dp.size(); ++i)
  14.         {
  15.             dp[i] = (s[i - 1] == '0') ? 0 : dp[i - 1];
  16.             if (i > 1 && (s[i - 2] == '1' || (s[i - 2] >= '2' && s[i - 1] <= '6')))
  17.                 dp[i] += dp[i - 2];
  18.         }
  19.         return dp[s.size()];
  20.     }
  21. };
  22.  
  23. int main()
  24. {
  25. Solution s;
  26. cout << s.numDecodings("12") << endl;
  27. cout << s.numDecodings("226") << endl;
  28. cout << s.numDecodings("0") << endl;
  29. cout << s.numDecodings("06") << endl;
  31. return 0;
  32. }

代码6：  

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Solution
  5. {
  6. public:
  7. int numDecodings(string s) {
  8.     if (s.empty() || s[0] == '0') {
  9.         return 0;
  10.     }
  11.     vector<int> dp(s.size() + 1, 1);
  12.     for (int i = 2; i < dp.size(); ++i){
  13.         dp[i] = ((s[i-1] == '0') ? 0 : dp[i-1]);
  14.         if (s[i-2] == '1' || (s[i-2] == '2' && s[i-1] <= '6')){
  15.             dp[i] += dp[i-2];
  16.         }
  17.     }
  18.     return dp.back();
  19. }
  20. };
  21.  
  22. int main()
  23. {
  24. Solution s;
  25. cout << s.numDecodings("12") << endl;
  26. cout << s.numDecodings("226") << endl;
  27. cout << s.numDecodings("0") << endl;
  28. cout << s.numDecodings("06") << endl;
  30. return 0;
  31. }

前：​https://hannyang.blog.csdn.net/article/details/129287197​

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览51117 人正在系统学习中
PythonTogether
微信公众号
一起来学派森吧
【算法系列篇】滑动窗口
走进人工智能|深度学习 算法的创世纪