C++任意四边形的面积

class Solution {
public:int numDistinct(string s, string t) {vector<vector<long long>> dp(s.size()+1,vector<long long>(t.size()+1));//为什么要这样初始化：
//dp[i][0] 表示：以i-1为结尾的s可以随便删除元素，出现空字符串的个数。
//那么dp[i][0]一定都是1，因为也就是把以i-1为结尾的s，删除所有元素，出现空字符串的个数就是1。for (int i = 0; i <= s.size(); i++) dp[i][0] = 1;for(int i=1;i<=s.size();i++){for(int j=1;j<=t.size();j++){if(s[i-1]==t[j-1]){dp[i][j]=(dp[i-1][j]+dp[i-1][j-1])%INT_MAX;}//为什么这样推：
//当最后一位相等时,以s = "rara" t = "ra" 为例，当i = 4, j = 2时，s[i] == t[j]。
//此时分为2种情况，s串用最后一位的a + 不用最后一位的a。
//如果用s串最后一位的a,那么t串最后一位的a也被消耗掉，此时的子序列其实=dp[i-1][j-1]
//如果不用s串最后一位的a，那就得看"rar"里面是否有"ra"子序列的了，就是dp[i-1][j]
//再看s[i] != t[j] 比如 s = "rarb" t = "ra" 还是当i = 3, j = 1时，s[i] != t[j]
//此时显然最后的b想用也用不上啊。所以只能指望前面的"rar"里面是否有能匹配"ra"的
//所以此时dp[i][j] = dp[i-1][j]else{dp[i][j]=(dp[i-1][j])%INT_MAX;}//不能返回最大值，比如s=eee;j=eee;//此时返回值为1，而不是最大值3；}}return dp[s.size()][t.size()];}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！