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