百度3.29 算法岗笔试第二题 RGB括号涂颜色

Quinta ·

更新时间:2024-11-10

· 655 次阅读

题目省略
大体思路：多状态的动态规划，以一对括号为动态规划最小单元，从第一个出现的右括号所在的那对括号开始，从里向外。

动态方程为：
一、如果当前括号里面还有括号：
当前左括号为红色的总可能方案=里面那个左括号为红色的总方案+里面那个左括号为绿色的总方案2+里面那个左括号为蓝色的总方案2

当前左括号为绿色的总可能方案=里面那个左括号为红色的总方案+里面那个左括号为蓝色的总方案

当前左括号为蓝色的总可能方案=里面那个左括号为红色的总方案+里面那个左括号为绿色的总方案

二、如果当前括号在前面计算过的括号的右边，如（（））（）中的右边那对括号：
当前左括号为红色的总可能方案=前面括号所有方案总和+2
当前左括号为绿色的总可能方案=前面括号所有方案总和+1
当前左括号为蓝色的总可能方案=前面括号所有方案总和+1

def main():
    n = 6
    string = '((()))'
    stack = [0]
    memo=[]
    for i in range(1,n):
        if string[i]=='(':
            stack.append(i)
        else:
            ind=stack.pop()
            memo.append((ind,i))
    dp=[[0,0,0] for i in range(len(memo))]
    dp[0][0]=2
    dp[0][1]=1
    dp[0][2] = 1
    for i in range(1,len(memo)):
        if memo[i][0]<memo[i-1][0]:
            dp[i][0]=dp[i-1][0]+dp[i-1][1]*2+dp[i-1][2]*2
            dp[i][1]=dp[i-1][0]+dp[i-1][2]
            dp[i][2]=dp[i-1][0]+dp[i-1][1]
        else:
            dp[i][0]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]+2
            dp[i][0] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + 1
            dp[i][0] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + 1
    print (dp[len(memo)-1][0]+dp[len(memo)-1][1]+dp[len(memo)-1][2])
main()

作者：wxfnynl

rgb 算法

1024 个赞