关于#算法#的问题：难题求解答(语言-python)

Question

今日份刷题，卡在这道2022年蓝桥杯国赛题上了，在线请求指教。

1. 

Answer 1

引自免费微信小程序：皆我百晓生

为了解决这个问题，我们可以采用动态规划的方法。首先，我们需要定义一个二维数组dp，其中dp[i][j]表示前i个字符串中，以第j个字符结尾的owo子串的最大数量。状态转移方程如下：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]+(s[i-1][j] == 'o' && s[i-1][j+1] == 'w'))

这里，s[i][j]代表第i个字符串中的第j个字符。如果当前字符是'o'并且下一个字符是'w'，那么我们就可以增加一个owo子串。同时，我们还需要考虑不包括当前字符串的情况，因此需要比较dp[i-1][j]（不包括当前字符串）和dp[i-1][j-1]+(s[i-1][j] == 'o' && s[i-1][j+1] == 'w')（包括当前字符串）两个情况，取较大值作为dp[i][j]。

下面是完整的Python代码实现：

def count_owo(strings):
    n = len(strings)
    dp = [[0] * (len(strings[0]) + 2) for _ in range(n)]
    
    for i in range(n):
        if strings[i].startswith('o'):
            dp[i][1] = 1
    
    for i in range(1, n):
        for j in range(1, len(strings[i])):
            if strings[i][j] == 'o' and strings[i][j+1] == 'w':
                dp[i][j+2] = max(dp[i][j+2], dp[i-1][j] + 1)
            
            if i > 0:
                dp[i][j] = max(dp[i][j], dp[i-1][j])
                
                if j > 0:
                    dp[i][j] = max(dp[i][j], dp[i-1][j-1])

    result = [0] * n
    for i in range(n):
        for j in range(len(strings[i]), -1, -1):
            result[i] += dp[i][j]
    
    return result


strings = ["owo", "W", "Ow"]
print(count_owo(strings))

这段代码首先初始化了dp数组，并处理了字符串开头为'o'的情况。然后，通过两层循环遍历每个字符串中的每个字符，更新dp数组。最后，从后向前遍历dp数组，累加每个位置上的owo子串数量，得到结果列表。在给定的例子中，它会输出 [1, 1, 2]。