Python题解，动规解法 | #红和绿#

O(n)时间，O(n)空间动态规划解法

While True:
    try:
        s = input()
        n = len(s)
        #dp[i]: 使前i个正方形全红最少需要的染色数
        dp = []
        #计算dp[0]，即使所有正方形绿色需要的染色数
        count = 0
        for i in range(n):
            if s[i]=='R':
                count += 1
        dp.append(count)
        minChange = count
        i = 0
        #对于i>=0，如果s[i]是红色，dp[i] = dp[i-1]-1, 否则 dp[i]=dp[i-1]+1
        while(i<n):
            if s[i]=='R':
                count -= 1
            else:
                count += 1
            dp.append(count)
            i+=1
            minChange = min(minChange, count)
        print(minChange)
    except:
        break

O(n)时间，O(1）空间优化解法

While True:
    try:
        s = input()
        n = len(s)
        count = 0
        for i in range(n):
            if s[i]=='R':
                count += 1
        minChange = count
        i = 0
        while(i<n):
            if s[i]=='R':
                count -= 1
            else:
                count += 1
            i+=1
            minChange = min(minChange, count)
        print(minChange)
    except:
        break