#每日一面BAT#第17题 RGB字符串


给一个字符串S,只包含R,G,B三种字符,起点在S[0],目标走到S[n-1], n为S的长度

规则:
1) 每次可走若干步,但必须从R到G, G到B,B到R
2) 每走一次,需要代价 (j-i)*(j-i) (从i走到j)

问最小需要的cost, 如果不存在这样的路径,返回-1

例子:
RGGGB
0->2->4, 需要的cost= 2*2+2*2 = 8
已邀请:

cpcs - 诚实努力

赞同来自: 天天 云凌


答案
其实这题就是一个最短路
如果i < j
(1) S[i] = 'R', S[j] = 'G', 建立一条(i - j) * (i - j) 的边
(2) S[i] = 'G',S[j] = 'B', 建立一条(i - j) * (i - j) 的边
(3) S[i] = 'B', S[j] = 'R', 建立一条(i - j) * (i - j)的边
求0到(n-1)的最短路。

当然 也可以动态规划
dp[x]表示到达x的最小代价
初值 dp[0] = 0
dp[j] = min(dp[i] + (i - j) * (i - j)) 如果i < j并且S[i] S[j]满足上面那个(1) (2) 或者(3)之一
求dp[n - 1]

其实两个方法是等价的……

要回复问题请先登录注册

收藏七月在线,一起向大牛进阶

ctrl+D或command+D可以快速收藏哦~