Блог пользователя Yellow.Flash

Help in a DP problem (google kickstart 2017)
Автор Yellow.Flash, история, 8 лет назад, По-английски

problem B google kickstart

Someone please explain the approach for this problem.

Thanks

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Yellow.Flash (previous revision, new revision, compare).

→ Ответить
»
8 лет назад, # |
← Rev. 3   Проголосовать: нравится +4 Проголосовать: не нравится

calc dp[i][j] -> is there a string, that suitable prefix i of the first template and the prefix j of the second pattern?

and then easy transitions:


dp[0][0] = true; 

if (a[i] != '*' && b[j] != '*' && a[i] == b[j])
{
    dp[i + 1][j + 1] |= dp[i][j];
}

if (a[i] == '*')
{
    dp[i + 1][j] |= dp[i][j];
    dp[i + 1][j + 1] |= dp[i][j];
}

if (b[j] == '*')
{
    dp[i][j + 1] |= dp[i][j];
    dp[i + 1][j + 1] |= dp[i][j];
}

answer in dp[n][m]

→ Ответить