1.題目
給定一個字串 s，計算 s 的 不同非空子序列 的個數，因為結果可能很大，所以回傳答案需要對 10^9 + 7 取余 ，
字串的 子序列 是經由原字串洗掉一些（也可能不洗掉）字符但不改變剩余字符相對位置的一個新字串，
- 例如，
"ace"是"abcde"的一個子序列，但"aec"不是，
示例 1：
輸入：s = "abc"
輸出：7
解釋：7 個不同的子序列分別是 "a", "b", "c", "ab", "ac", "bc", 以及 "abc"，示例 2：
輸入：s = "aba"
輸出：6
解釋：6 個不同的子序列分別是 "a", "b", "ab", "ba", "aa" 以及 "aba"，示例 3：
輸入：s = "aaa"
輸出：3
解釋：3 個不同的子序列分別是 "a", "aa" 以及 "aaa"，提示：
1 <= s.length <= 2000s僅由小寫英文字母組成
2.分析思路
這個方法是一個acmer和我一起慢慢分析得出，大致程序就是動態規劃，
設狀態dp[i]: 以位置i結尾的子序列個數.如字串“abc”
dp[0]=1,就一個a;dp[1]=2,以字符b結尾的子序列的數目：b、ab;dp[2]=4;c,ac,bc,abc;
abc的子序列個數為dp[0]+dp[1]+dp[2]=1+2+4=7;
如字符"aba"
dp[0]=1,a;dp[2]=2,b,ab;dp[3]=3,aa,ba,aba;
aba子序列的個數為dp[0]+dp[1]+dp[2]=1+2+3=6;
從上述分析可以得出，當字串沒有重復字符時，dp[i+1]=dp[i]+dp[i-1]+....+dp[0]+1;
最后的子序列的個數：
但是當字串中有重復子串的時候：
需要減去重復的值，并且更新i位置的dp[i]及之后的dp[i+1].....
如字符"aba"
dp[0]=1,a;
dp[2]=2,b,ab;
dp[3]=3=(4-1),aa,ba,aba,(a);
aba子序列的個數為dp[0]+dp[1]+dp[2]=1+2+3=6;
這我實作的不太好，使用了暴力方法進行遍歷dp，更新dp，時間復雜度較高，
3.代碼實作
class Solution {
public int sum=0;
public int summ(int a[],int num)
{
int results=0;
for(int i=0;i<num;i++)
{
//System.out.println("遍歷num:"+a[i]);
results=(int)((results+a[i])%(Math.pow(10,9)+7));
}
return results;
}
public int distinctSubseqII(String s) {
int results=0;
Map<Character,ArrayList<Integer>>map=new HashMap<Character,ArrayList<Integer>>();//資料結構
int leng=s.length();
int nums[] =new int[leng];
nums[0]=1;
double M=Math.pow(10,9)+7;
for(int i=0;i<s.length();i++)//獲取是否重復的值
{
//ArrayList<Integer> list=new ArrayList<Integer>();
Character c=s.charAt(i);
boolean b = map.containsKey(c);
if(b)
{
//System.out.println("存在"+b);
ArrayList<Integer> value = https://www.cnblogs.com/echoqiqi/p/map.get(c);
value.add(i);
}
else
{
ArrayList value=new ArrayList();
value.add(i);
map.put(c,value);
}
}
for(int i=1;i
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/516385.html
標籤：其他
上一篇：【學習筆記】二分