[LeetCode] 115. Distinct Subsequences

😎풀이

백트레킹을 활용해 풀이하려 했으나 시간 초과가 발생하여 dp 풀이로 변경하였음

초기화를 위해 문자열보다 1만큼 큰 배열을 만들고 첫 열은 반드시 1로 설정되게 함

function numDistinct(s: string, t: string): number {
    // dp[i][j]: s의 i번째 위치에서 t의 j번째 문자까지 만들 수 있는 경우의 수
    const dp: Map<string, number> = new Map();
    
    function dfs(sIdx: number, tIdx: number): number {
        // t를 모두 만든 경우
        if (tIdx === t.length) return 1;
        // s를 모두 사용했지만 t를 못 만든 경우
        if (sIdx === s.length) return 0;
        
        const key = `${sIdx},${tIdx}`;
        if (dp.has(key)) return dp.get(key)!;
        
        let count = 0;
        // 현재 문자가 같은 경우
        if (s[sIdx] === t[tIdx]) {
            // 현재 문자를 사용하는 경우
            count += dfs(sIdx + 1, tIdx + 1);
        }
        // 현재 문자를 사용하지 않는 경우
        count += dfs(sIdx + 1, tIdx);
        
        dp.set(key, count);
        return count;
    }
    
    return dfs(0, 0);
}