本文主要是介绍【Leetcode】115. Distinct Subsequences，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Given two strings s and t, return the number of distinct subsequences of s which equals t.
The test cases are generated so that the answer fits on a 32-bit signed integer.
Example 1:
Input: s = "rabbbit", t = "rabbit"
Output: 3
Explanation:
As shown below, there are 3 ways you can generate "rabbit" from s.
rabbbit
rabbbit
rabbbit
Example 2:
Input: s = "babgbag", t = "bag"
Output: 5
Explanation:
As shown below, there are 5 ways you can generate "bag" from s.
babgbag
babgbag
babgbag
babgbag
babgbag
Constraints:
1 <= s.length,
t.length <= 1000
s and t consist of English letters.
AC:
/** @lc app=leetcode.cn id=115 lang=cpp** [115] 不同的子序列*/// @lc code=start
class Solution {
public:int numDistinct(string s, string t) {vector<vector<uint64_t>> dp(s.size() + 1, vector<uint64_t>(t.size() + 1));for(int i = 0; i < s.size(); i++) {dp[i][0] = 1;}for(int j = 1; j < t.size(); j++) {dp[0][j] = 0;}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 - 1] + dp[i - 1][j];} else {dp[i][j] = dp[i - 1][j];}}}return dp[s.size()][t.size()];}
};
// @lc code=end
RE:
/** @lc app=leetcode.cn id=115 lang=cpp** [115] 不同的子序列*/// @lc code=start
class Solution {
public:int numDistinct(string s, string t) {vector<vector<long long>> dp(s.size() + 1, vector<long long>(t.size() + 1));for(int i = 0; i < s.size(); i++) {dp[i][0] = 1;}for(int j = 1; j < t.size(); j++) {dp[0][j] = 0;}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 - 1] + dp[i - 1][j];} else {dp[i][j] = dp[i - 1][j];}}}return dp[s.size()][t.size()];}
};
// @lc code=end
在C++中，uint64_t和long long都是整数类型，但它们有一些区别。
uint64_t是无符号64位整数类型，它在内存中占用8个字节，可以表示0到18446744073709551615之间的整数。long long是有符号的64位整数类型，它在内存中也占用8个字节，可以表示-9223372036854775808到9223372036854775807之间的整数。
因为uint64_t是无符号的，所以它只能表示非负数，而long long既可以表示正数也可以表示负数。所以，在使用这两种类型时需要注意，如果需要表示负数，应该使用long long；如果不需要表示负数，应该使用uint64_t，因为它的取值范围比long long更大。
这篇关于【Leetcode】115. Distinct Subsequences的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
