我在动态编程中遇到了这些问题,我需要提供一个基于动态编程的解决方案:
我们有长度为n的字符串,并且只包含{A,B,C}charachters.string只有在一行中不包含3个A并且最多包含一个B时才是“winner”。
例子:
有43个长度为4的“赢家”字符串。
我需要提出一种算法,它计算长度为n的“获胜”字符串的数目,它需要以O(n)复杂度运行。
到目前为止我想的是:
3参数:n-当前字符串的长度,bCount=1,aCount=2。
在每次迭代中,n减少1如果我们使用b,那么计数减少1如果我们使用一个so-acount递减1,但如果插入了其他字符,则它初始化为2。
我需要使它正式和明确,希望你能帮助我填补空白,使解决方案正式。
我真的很努力想解决它,如果有人能帮助我,我会非常感谢。
提前谢谢你。

最佳答案

首先让我们看看b。你要么没有b,因此只有a和c的长度为n的字符串,要么你有一个只有a和c的长度为n-1的1 b和2个子字符串的字符串。因此,如果你能计算出任意长度字符串的所有有效a和c组合,剩下的就很容易了。

function winners(n) {
    let sum = combos[n]
    for (let i = 0; i < n; i++)
        sum += combos[i] * combos[n - i - 1]
    return sum
}

如何计算a,c组合?可以使用动态编程(始终查看A、C和AA中有多少字符串结尾):
combos = [1, 2]
endsInA = 1
endsInC = 1
endsInAA = 0
for (let i = 2; i <= n; i++) {
    combos[i] = (endsInA + endsInC) * 2 + endsInAA
    let c = endsInC
    endsInC = endsInA + endsInAA + c
    endsInAA = endsInA
    endsInA = c
}

它是(endsInA + endsInC) * 2 + endsInAA因为在以a或c结尾之后,您可以放置a或c,而在以aa结尾之后,您只能放置c。更新规则也很容易理解。以A A结尾的字符串和以before结尾的字符串一样多,以A结尾的字符串和以C结尾的字符串一样多C可以放在所有字符串后面,所以它只是以前所有可能的结尾的总和你也可以先更新,然后取所有结尾的和得到组合的数目。
Everything put together and optimized for a demo
用O(n)来计算组合和O(n)来计算优胜者,因此整个复杂性是O(n)。

09-19 23:25