Balanced Cow Breeds

   Size parantezlerden oluşan N uzunluğunda bir dizi veriliyor. Bu parantezleri H ve G grubu olarak ikiye ayıracaksınız, öyle ki her iki grubun parantezleri kendi içinde düzenli parantez olacak. Sizden bunun kaç farklı şekilde yapılabileceğini bulmanız isteniyor. Çıktıya 2012'ye göre modunu yazdırıyorsunuz.    Düzenli parantez dizileri açma ve kapama parantezleri sayısının birbirine eşit olduğu ve soldan sağa giderken kapamaların sayısının açmaları hiçbir zaman geçmediği parantez dizileridir. Örneğin: "()","(())", "(())()"

Kısıtlamalar

1 <= N <= 1000

Girdi Formatı

Tek satırda parantezlerden oluşan N uzunluğunda dizi

Örnek Girdi

(())

Çıktı Formatı

Tek satırda istenenin kaç farklı şekilde yapılabileceğinin 2012'ye göre modu.

Örnek Çıktı

6

Çıktı Açıklaması

6 gruplama:

(())
HHHH

(())
GGGG

(())
HGGH

(())
GHHG

(())
HGHG

(())
GHGH

ÇÖZÜM

Soru iki boyutlu dinamik kullanılarak çözülebilir. dp[i][j] sunu belirtiyor: i indisine kadar olan parantezleri bir sekilde gruplamisim ve H grubuna aldigim acmalarin sayisi kapamalarinkinden j fazla iken i ile n arasini kac farkli sekilde uygun sekilde gruplandirabilirim. Herhangi bir durumda iki secim yapabilirim: i. parantez ya H olacak ya da G. Dinamik yapmadan once dizinin her bir indisi icin oraya kadarki "acmalar - kapamalar"i hesaplamak dinamigi yaparken ise yarayacaktir.