ID: 617

Difficulty: 6

所属公司 : 腾讯音乐

时间 :2023年9月22日

题目描述

小红需要构造一个串 $s$ 为串 $t$ ，初始串 $s$ 为空。

思路：动态规划

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

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