链接https://www.lintcode.com/problem/1702/description940. 不同的子序列 II - 力扣LeetCode题解dp[i]表示以下标i为结尾的非空子序列的个数sun{0, i}1.倒序遍历ji-1开始判断是否能从j的位置到i如果s[j] s[i]说明j-1前面的字符串可以到s[j]没必要到后面再出现的s[i]了class Solution { public: /** * param s: The string s * return: The number of distinct, non-empty subsequences of S. */ int distinctSubseqII(string s) { int MOD 1000000007; // Write your code here if (s.size() 0) { return 0; } std::vectorint dp(s.size()); std::unordered_setchar visited; for (int i 0; i s.size(); i) { if (visited.find(s[i]) ! visited.end()) { continue; } dp[i] 1; visited.insert(s[i]); } for (int i 0; i s.size(); i) { for (int j i-1; j 0; --j) { dp[i] (dp[i] dp[j]) % MOD; if (s[i] s[j]) { break; } } } int result 0; for (auto num : dp) { result (result num) % MOD; } return result; } };Chapter 11.动态规划进阶上