[刷题笔记] 115.Distinct Subsequences

题目

解析

第一个如果没想到动态规划就out了。

首先确定dp的定义。

dp[i][j]表示 s[0…i] 与 t[0…j] 之间的Distinct Subsequences的个数。

然后确定初始状态。

dp[0][0] 自然是比较 s[0] t[0] 是否相等。

dp[i][0] 可以通过遍历s，数出有多少s[i] 与 t[0] 相等。

tp[0][j] 相对比较简单，除了 dp[0][0] 之外，都是 0。

接着确定状态转移。

当 s[i] == s[j] 的时候，dp[i][j] = dp[i-1][j-1] + dp[i-1][j]（这个是蒙的，不过也不难蒙）

解法

def num_distinct(s, t)
    ls = s.length
    lt = t.length
    dp = Array.new(ls){Array.new(lt)}
    
    count = 0
    for i in 0...ls
        count += 1 if s[i] == t[0]
        dp[i][0] = count
    end
    
    for i in 1...lt
        dp[0][i] = 0
    end
    
    for i in 1...ls
        for j in 1...lt
            if s[i] == t[j]
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
            else
                dp[i][j] = dp[i-1][j]
            end
        end
    end
    return dp[ls-1][lt-1]
end

双百分。