SRM471 Div2 Medium(500) EllysPlaylists

EllysPlaylists

動的計画法。長さkで最後の曲がiであるプレイリストの数をnum[k][i]とすると、
num[k][i] = num[k-1][j₁] + num[k-1][j₂] + ……。
ただし、j₁, j₂, ……はi番目の曲の先頭3文字と末尾3文字が一致する曲の番号。

#include <string>
#include <vector>

using namespace std;

class EllysPlaylists
{
public:
    int countPlaylists( vector <string> songs, int K );
};

int EllysPlaylists::countPlaylists( vector <string> songs, int K )
{
    int n = (int)songs.size();

    vector<vector<int> > num( K, vector<int>( n ) );

    for ( int i=0; i<n; i++ )
        num[0][i] = 1;

    for ( int k=1; k<K; k++ )
    for ( int i=0; i<n; i++ )
    {
        num[k][i] = 0;

        for ( int j=0; j<n; j++ )
            if ( songs[j].substr(songs[j].length()-3,3) == songs[i].substr(0,3) )
                num[k][i] = ( num[k][i] + num[k-1][j] ) % 1000000007;
    }

    int ans = 0;
    for ( int i=0; i<n; i++ )
        ans = ( ans + num[K-1][i] ) % 1000000007;

    return ans;
}