藍(lán)跳跳（動(dòng)態(tài)規(guī)劃）
【問(wèn)題描述】
小藍(lán)制作了一個(gè)機(jī)器人，取名為藍(lán)跳跳览绿，因?yàn)檫@個(gè)機(jī)器人走路的時(shí)候基本靠跳躍。
藍(lán)跳跳可以跳著走穗慕，也可以掉頭饿敲。藍(lán)跳跳每步跳的距離都必須是整數(shù)，每步可以跳不超過(guò) k 的長(zhǎng)度逛绵。由于藍(lán)跳跳的平衡性設(shè)計(jì)得不太好怀各，如果連續(xù)兩次都是跳躍倔韭，而且兩次跳躍的距離都至少是 p，則藍(lán)跳跳會(huì)摔倒瓢对，這是小藍(lán)不愿意看到的寿酌。
小藍(lán)接到一個(gè)特別的任務(wù)，要在一個(gè)長(zhǎng)為 L 舞臺(tái)上展示藍(lán)跳跳沥曹。小藍(lán)要控制藍(lán)跳跳從舞臺(tái)的左邊走到右邊份名，然后掉頭，然后從右邊走到左邊妓美，然后掉頭僵腺，然后再?gòu)淖筮呑叩接疫叄缓蟮纛^壶栋，再?gòu)挠疫呑叩阶筮叧饺纾缓蟮纛^，如此往復(fù)贵试。為了讓觀者不至于太無(wú)趣琉兜，小藍(lán)決定讓藍(lán)跳跳每次用不同的方式來(lái)走。小藍(lán)將藍(lán)跳跳每一步跳的距離記錄下來(lái)，按順序排成一列，顯然這一列數(shù)每個(gè)都不超過(guò) k 且和是 L驶俊。這樣走一趟就會(huì)出來(lái)一列數(shù)。如果兩列數(shù)的長(zhǎng)度不同梧疲，或者兩列數(shù)中存在一個(gè)位置數(shù)值不同，就認(rèn)為是不同的方案运准。
請(qǐng)問(wèn)藍(lán)跳跳在不摔倒的前提下幌氮，有多少種不同的方案從舞臺(tái)一邊走到另一邊。
【輸入格式】
輸入一行包含三個(gè)整數(shù) k, p, L胁澳。
【輸出格式】
輸出一個(gè)整數(shù)该互，表示答案。答案可能很大韭畸，請(qǐng)輸出答案除以 20201114 的余數(shù)宇智。
【樣例輸入】
3 2 5
【樣例輸出】
9
【樣例說(shuō)明】
藍(lán)跳跳有以下 9 種跳法：
1+1+1+1+1
1+1+1+2
1+1+2+1
1+2+1+1
2+1+1+1
2+1+2
1+1+3
1+3+1
3+1+1
【樣例輸入】
5 3 10
【樣例輸出】
397
方法一
思路：
這種題可以用遞歸的DFS解也可以用動(dòng)態(tài)規(guī)劃，相比較經(jīng)典的遞歸走臺(tái)階問(wèn)題胰丁，由于題目沒(méi)有限定第一步跳的種類普筹，所有導(dǎo)致有多種方法。遞歸之后也是無(wú)法求解;遞歸無(wú)法求解的題目隘马。因?yàn)橹貜?fù)計(jì)算。計(jì)算規(guī)模o(L的k次方)妻顶，所以采用了動(dòng)態(tài)規(guī)劃+遞推做的此題酸员，我們可以建立一個(gè)2維數(shù)組dp[i][j] 蜒车。
i 表示舞臺(tái)距離，j表示第一次跳j格時(shí)幔嗦。 dp[i][j]表示我當(dāng)前步數(shù)用j步走 可以多少種方法走到i酿愧。
p意思就是連續(xù)跳大于等于p時(shí)就會(huì)摔倒。
d[i][j]i跳數(shù)的取值范圍0-K
j的取值范圍是0-L
規(guī)律描述：當(dāng)舞臺(tái)長(zhǎng)度為1時(shí)邀泉，我第一步為1時(shí)dp[1][1]=1 種方法 當(dāng)?shù)谝徊綖?時(shí) d[1][2]=0種嬉挡。當(dāng)?shù)谝徊綖?時(shí)dp[1][3]=0種。
當(dāng)舞臺(tái)長(zhǎng)度為2時(shí)汇恤，我第一步為1時(shí)dp[2][1]=1種方法 當(dāng)?shù)谝徊綖?時(shí)dp[2][2]=1種庞钢。當(dāng)?shù)谝徊綖?時(shí)dp[2][3]=0種.
當(dāng)我們得到長(zhǎng)度為2 第一步為1時(shí)， 我當(dāng)前的長(zhǎng)度減1 剩余舞臺(tái)長(zhǎng)度為1因谎，我們可以看到舞臺(tái)為1的時(shí)候一共只有1種方法那么當(dāng)長(zhǎng)度為dp[1][1]+dp[1][2]+dp[1][3]=dp[2][1]=1 第一步為1時(shí)就是一種方法基括。因?yàn)楫?dāng)跳的步數(shù)和長(zhǎng)度相等的時(shí)候只有一種方法 dp[2][2]=1。
如果連續(xù)兩次都是跳躍财岔，而且兩次跳躍的距離都至少是 p风皿，我們知道j是第一種跳法，k就是第2個(gè)選擇的跳法所以 j>=b 分為二種轉(zhuǎn)移方程匠璧，
當(dāng)j>=b , 說(shuō)明我們第一次跳了大于p的距離如果我們第二次在大于p那么藍(lán)跳跳將會(huì)摔倒所以我們dp[4][2]+=dp[2][1] 不可以選擇dp[2][2]和dp[2][3]
那么轉(zhuǎn)移方程得：dp[i][j]+=dp[i-j][k]
當(dāng)?shù)谝淮涡∮趐的長(zhǎng)度桐款，我們第二次就把所有可能選擇上dp[4][1]=dp[3][1]+dp[3][2]+dp[3][3]
那么轉(zhuǎn)移方程得：dp[i][j]+=sum(dp[i-j])。
但是這種不是最優(yōu)解最多跑80%的數(shù)據(jù)夷恍。
程序：
#i 總步數(shù)
#j 跳一次的步數(shù)
p,b,s=map(int,input().split())
o=0
dp=[[0 for i1 in range(p+1) ] for i in range(s+1)]
dp[1][1]=1
for i in range(2,s+1):
for j in range(1,p+1):
if i-j==0:
dp[i][j]+=1
elif j>=b:
for k in range(1,b):
dp[i][j]+=dp[i-j][k]%20201114
else:
dp[i][j]+=sum(dp[i-j])%20201114
print(sum(dp[s])%20201114)
方法二
思路：
創(chuàng)建一個(gè)雙層的循環(huán)數(shù)組魔眨，0層存j<b的方式個(gè)數(shù)，1層存b<p+1方式個(gè)數(shù)裁厅。和上面方法差不多只不過(guò)是以雙層的格式存儲(chǔ)冰沙，這樣可以少很多的計(jì)算量。
我們先把已知的數(shù)據(jù)寫入二維數(shù)據(jù)中dp[1][0]=1执虹，然后遍歷2,s+1和1,p+1,因?yàn)楫?dāng)s=0時(shí) 方法只有一種拓挥。把dp[0][1]=1 或者dp[0][0]=1 我只是把這個(gè)當(dāng)上面方法dp[i][j]+=1用了。
這個(gè)轉(zhuǎn)移方程也是2個(gè)袋励，一個(gè) (1,b) 和(b,p+1) 把j<b 存在dp[i][0] b<p+1存在dp[i][1]侥啤。
轉(zhuǎn)移方程分別為 dp[i][0]+=dp[i-j][1]+dp[i-j][0]， dp[i][1]+=dp[i-j][0]茬故。
這種就可以把數(shù)據(jù)跑完了計(jì)算量把上個(gè)方法少了很多盖灸。
p,b,s=map(int,input().split())
dp=[[0 for i1 in range(2) ] for i in range(s+1)]
dp[0][1]=1
dp[1][0]=1
for i in range(2,s+1):
for j in range(1,b):
if i-j<0:
break
dp[i][0]+=((dp[i-j][1]+dp[i-j][0])%20201114)
for j in range(b,p+1):
if i-j<0:
break
dp[i][1]+=dp[i-j][0]%20201114
print(sum(dp[s])%20201114)
