ID: 617

Type: Default

1000ms

256MiB

Difficulty: 6

Uploaded By:

Tags>

腾讯音乐

题目描述

塔子哥需要构造一个串 $s$ 为串 $t$ ，初始串 $s$ 为空。

思路：动态规划

$f[i]$ 表示构造出 $t$ 的前 $i$ 个字符的不同方案数。

在末尾添加第 $i$ 个字符： $f[i]=f[i] + f[i-1]$