leetcode 动态规划类型题

怼烎@ 2021-12-03 08:10 237阅读 0赞

1，Triangle

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 int mininumTotal(vector<vector<int>>& triangle)  {
    2     for (int i = triangle.size() - 2; i >= 0; --i) {  
    3         for (int j = 0; j < i + 1; ++j) {
    4             // 从下往上依次保存当前路径的最小值，上层只会用到下层的最小值
    5             triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1]);
    6         }
    7     }
    8     return triangle[0][0];
    9 }

triangle

2，Maximum SubArray

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
     2  * 状态转移方程为：f[j] = max{ f[j-1] + S[j],S[j] },其中  1 <= j <= n
     3  *                 target = max{ f[j] },其中  1 <= j <= n
     4 */
     5 int maxArray(vector<int>& nums) {
     6     int n = nums.size();
     7     vector<int> dp(n + 1);
     8     dp[0] = 0;
     9     for (int i = 0; i < n; ++i) {
    10         dp[i + 1] = max(dp[i] + nums[i], nums[i]);
    11     }
    12     return *max_element(dp.begin(), dp.end());

maxArray

3，Palindromic Substrings

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
     2 * dp[i][j] 的值表示 s[i,j]这个字串是否为回文字符串
     3 */
     4 int countSubstrings(string& s) {
     5     int n = s.size();
     6     int res = 0;
     7     vector<vector<bool>> dp(n, vector<bool>(n, false));
     8     for (int i = n - 1; i >= 0; i--) {
     9         for (int j = i; j < n; ++j) {
    10             dp[i][j] = (s[i] == s[j] && (j - i <= 2 || dp[i + 1][j - 1]));
    11             if (dp[i][j]) res++;
    12         }
    13     }
    14     return res;
    15 }

countSubstrings

4，Palindromic Substrings(II)

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
     2 * p[i][j]用来判断 s[i][j]这个字串是否是回文子串
     3 * dp[i] 用来记录[0,i]这个范围内的最小切割数
     4 * 所以只用求 dp[n-1] 的值就是答案
     5 */
     6 int minCut(string& s) {
     7     if (s.empty()) return 0;
     8     int n = s.size();
     9     vector<vector<bool>> p(n, vector<bool>(n));
    10     vector<bool> dp(n);
    11 
    12     for (int i = 0; i < n; ++i) {
    13         dp[i] = i;  // 对 dp[i]初始化为最大切割数
    14         for (int j = 0; j <= i; ++j) {  // 对每一个子串s[i][j]进行遍历
    15             if (s[i] == s[j] && (i - j <= 2 || p[j + 1][i - 1])) {  // 如果s[j][i] 为回文子串
    16                 p[j][i] = true;
    17                 dp[i] = (j == 0) ? 0 : min(dp[i], dp[j - 1] + 1);
    18             }
    19         }
    20     }
    21     return dp[n - 1];
    22 }

minCut

5,Longest Common Substring

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
     2  × 求解最长公共子串（一定是连续才称为子串）
     3  × 初始化：dp[0][j] = 0;dp[i][0] = 0; 第0行全为0,第0列全为0
     4  ×                           0 ; (i==0 || j==0)
     5  * 状态转移方程： dp[i][j] = dp[i-1][j-1] + 1;   (s1[i] == s2[j])
     6  *                           0 ; (s1[i] != s2[j])
     7  × 结果：每次保存字符串长度的最大值即为所求
     8  */
     9 int lcs(string s1,string s2) {
    10     int len1 = s1.length();
    11     int len2 = s2.length();
    12     int res = 0;
    13     vector<vector<int>> dp(len1+1,vector<int>(len2+1,0));
    14 
    15     for(int i=1;i<=len1;++i) {
    16         for(int j=1;j<=len2;++j) {
    17             if(s1[i] == s2[j]) dp[i][j] = dp[i-1][j-1] + 1;
    18             res = max(res,dp[i][j]);
    19         }
    20     }
    21     return res;
    22 }
    23 
    24 /*
    25  * 求解最长子序列（不一定连续）
    26  × 初始化：dp[0][j] = 0;dp[i][0] = 0;
    27  *                                 0;             (i == 0 || j == 0)
    28  × 状态转移方程：dp[i][j] =   dp[i-1][j-1] + 1;   (s1[i] == s2[j])
    29  *                          max(dp[i-1][j],dp[i][j-1]);(s1[i] != s2[j])
    30  * 结果：最后保存的 dp[len1][len2] 即为所求
    31  */
    32 int lcs(string s1,string s2) {
    33     int len1 = s1.length();
    34     int len2 = s2.length();
    35     vector<vector<int>> dp(len1+1,vector<int>(len2+1,0));
    36     
    37     for(int i=1;i<=len1;++i) {
    38         for(int j=1;j<=len2;++j) {
    39             if(s1[i] == s2[j]) dp[i][j] = dp[i-1][j-1] + 1;
    40             else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
    41         }
    42     }
    43     return dp[len1][len2];
    44 }

lcs

转载于:https://www.cnblogs.com/zpcoding/p/10746370.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211203/91c07cbe83dd4752bb0d1cf111f5fa87.png