Don't know if it's the best in terms of optimization, but you can make a texture that tiles horizontally and use that on the different levels of the stairs and offset flip the UV channels for every step. Then you can cut into the geometry to break up the silhouette a bit. Use vertex colors to get AO on the edges of the stairs, it may require you adding more geometry so it shades well, but a better tradeoff in my mind than making a unique staircase.
Replies
http://www.neogaf.com/forum/showthread.php?t=435670