3. Dynamic Programming

links

dp 分类:
LIS | LCS
区间dp( OI 区间dp | dp区间入门)

---

Sum: k n 问题

int waysOfSumGreater(int n,int k){
    int dp[n+2][n+2];
    memset(dp,0,sizeof(dp));
    for(int i=1;i<n+1;i++){
        dp[i][i]=1;
        for(int j=i-1;j>=1;j--){
            dp[i][j]=dp[i][j+1]+dp[i-j][j];
        }
    }
    return dp[n][k];
}
int waysOfSumLess(int n,int k){
    int dp[n+1][n+1];
    memset(dp,0,sizeof(dp));
    for(int j=0;j<n+1;j++){
        dp[0][j]=1;
    }
    for(int i=1;i<n+1;i++){
        dp[i][0] = 0;
        dp[i][1] = 1;
        for(int j=2;j<n+1;j++){
            if(j>i)
                dp[i][j] = dp[i][i];
            else
                dp[i][j] = dp[i][j-1]+dp[i-j][j];
        }

    }
//    for(int i=0;i<n+1;i++){
//        for(int j=0;j<n+1;j++)
//            cout<<dp[i][j]<<" ";
//        cout<<endl;
//    }
    return dp[n][k];
}

4. Greedy

vector<string> splitString(string s,string delimiter){
    size_t pos=0;
    vector<string> result;
    while((pos=s.find(delimiter))!=std::string::npos){
        string token = s.substr(0,pos);
        result.push_back(token);
        s.erase(0,pos+delimiter.size());
    }
    //"1,2,3" last without token
    result.push_back(s);
    return result;
}
vector<string> splitString(string s,string delimiter){
    auto start = 0U;    //unsigned integer
    auto end = s.find(delimiter);
    vector<string> result;
    while(end!=std::string::npos){
        string token = s.substr(start,end-start);
        result.push_back(token);
        start = end+delimiter.size();
        end = s.find(delimiter,start);
    }
    //"1,2,3" last without token
    result.push_back(s.substr(start,end));
    return result;
}

5. Backtrack