您的位置: 首页  >  IT文章  >  leetcode 动态规划类型题

leetcode 动态规划类型题

分类: IT文章 • 2025-02-04 10:32:43

1，Triangle

leetcode 动态规划类型题 
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

leetcode 动态规划类型题 
 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

leetcode 动态规划类型题 
 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)

leetcode 动态规划类型题 
 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

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-1] == s2[j-1]) 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-1] == s2[j-1]) 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

 6: 最长连续递增序列

//LongestIncrSequence 最长连续递增序列
int LongestIncrSequence(vector<int> v) {
    int size = v.size();
    int maxLen = 1;
    //dp[i] 表示从下标 i 开始到末尾的最长连续递增序列
    vector<int> dp(size, 1);
    for(int i=size-1; i>=0; i--) {
        for(int j=i+1; j<size; j++) {
            if(v[i] < v[j]) {
                dp[i] = max(dp[i], dp[j]+1);
                maxLen = max(maxLen, dp[i]);
            }
        }
    }
    return maxLen;
}

相关推荐