有一個(gè)長(zhǎng)度為?arrLen?的數(shù)組，開始有一個(gè)指針在索引?0 處。
每一步操作中，你可以將指針向左或向右移動(dòng) 1 步，或者停在原地（指針不能被移動(dòng)到數(shù)組范圍外）。
給你兩個(gè)整數(shù)?steps 和?arrLen ，請(qǐng)你計(jì)算并返回：在恰好執(zhí)行?steps?次操作以后，指針仍然指向索引?0 處的方案數(shù)。
由于答案可能會(huì)很大，請(qǐng)返回方案數(shù) 模?10^9 + 7 后的結(jié)果。
示例 1：輸入：steps = 3, arrLen = 2
? ? ? ? ? ? ? 輸出：4
? ? ? ? ? ? ? 解釋：3 步后，總共有 4 種不同的方法可以停在索引 0 處。
????????????????????????向右，向左，不動(dòng)
????????????????????????不動(dòng)，向右，向左
????????????????????????向右，不動(dòng)，向左
????????????????????????不動(dòng)，不動(dòng)，不動(dòng)
示例? 2：輸入：steps = 2, arrLen = 4
? ? ? ? ? ? ? ?輸出：2
? ? ? ? ? ? ? ?解釋：2 步后，總共有 2 種不同的方法可以停在索引 0 處。
? ? ? ? ? ? ? ? ? ? ? ? ? 向右，向左
? ? ? ? ? ? ? ? ? ? ? ? ? 不動(dòng)，不動(dòng)
解題思路：使用動(dòng)態(tài)規(guī)劃：
? ? ? ? ? ? ? ? 1.確定狀態(tài)：dp[i][j]為在i步操作下到達(dá)下標(biāo)j的方案數(shù)；
? ? ? ? ? ? ? ? 2.確定狀態(tài)轉(zhuǎn)移方程：dp[i][j] = dp[i-1][j-1] + dp[i-1][j] + dp[i-1][j+1]
? ? ? ? ? ? ? ? 3.確定開始條件及邊界條件：dp[0][0] = 1; dp[0][j>0] = 0; 0<=i<=steps; 0<=j<=steps or arrlen.
? ? ? ? ? ? ? ? 4.計(jì)算順序：dp[0][0]——>dp[1][0]——>dp[1][1]——>dp[1][2]......
class?Solution?{
????public?int?numWays(int?steps,?int?arrLen)?{
????????final?int?MODULO?=?1000000007;
????????int?maxIndex?=?Math.min(steps,?arrLen-1);
????????int[][]?dp?=?new?int[steps+1][maxIndex+1];
????????dp[0][0]?=?1;
????????for(int?i=1;?i<=steps;?i++)?{
????????????for(int?j=0;?j<=maxIndex;?j++)?{
????????????????dp[i][j]?=?dp[i-1][j];
????????????????if(j+1?<=?maxIndex)?{
????????????????????dp[i][j]?=??(dp[i][j]?+?dp[i?-?1][j?+?1])?%?MODULO;
????????????????}
????????????????if(j-1?>=?0)?{
????????????????????dp[i][j]?=?(dp[i][j]?+?dp[i?-?1][j?-?1])?%?MODULO;
????????????????}
????????????}
????????}
????????return?dp[steps][0];
????}
}
? ??????????????
? ? ? ??
