动态规划 Leetcode 392 判断子序列

admin2024-04-03  2

判断子序列

Leetcode 392

学习记录自代码随想录

要点:1.dp[i]以nums[i-1]结尾时最大子数组和,此时不用初始化dp[0]为nums[0],如果为nums[i]结尾则需要初始化;
2.递推公式: dp[i] = max(nums[i-1], dp[i-1] + nums[i-1]);
3.返回的是dp的最大值

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int m = s.size(), n = t.size();
        // s为空则一定为真
        if(m == 0) return true;
        // 1.dp[i][j]长度为s[0:i-1]和t[0:j-1]时最大重复子序列长度
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        // 2.递推公式:if(s[i-1] == t[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
        //            else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        // 3.dp数组初始化
        // 4.遍历顺序:正向遍历
        for(int i = 1; i < m+1; i++){
            for(int j = 1; j < n+1; j++){
                if(s[i-1] == t[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                if(dp[i][j] == m) return true;
            }
        }
        // 5.举例推导dp数组
        return false;
    }
};
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!