示例 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)

解題思路

數(shù)組含義

dp[i][j]代表第i步走到第j個(gè)下標(biāo)的方法數(shù)量

狀態(tài)轉(zhuǎn)移

dp[i][j]=dp[i-1][j];if(j-1>=0)dp[i][j]=(dp[i][j]+dp[i-1][j-1])%m;if(j+1<=maxL) dp[i][j]=(dp[i][j]+dp[i-1][j+1])%m;

要達(dá)到第i步走到第j個(gè)下標(biāo)這個(gè)狀態(tài)，要從上一步（i-1）的三種位置（j+1，j-1，j）轉(zhuǎn)移而來

上一步（i-1步）就是在當(dāng)前j位置不動(dòng)，所以dp[i][j]=dp[i-1][j];

上一步（i-1步）就是在當(dāng)前j位置的左邊（j-1），所以dp[i][j]=(dp[i][j]+dp[i-1][j-1])%m;

上一步（i-1步）就是在當(dāng)前j位置的右邊（j-1），所以dp[i][j]=(dp[i][j]+dp[i-1][j+1])%m;

初始化

剛開始時(shí)在第0個(gè)下標(biāo)，步數(shù)是0，所以方法數(shù)只有1（dp[0][0]=1）

代碼

class Solution {public int numWays(int steps, int arrLen) {int m=(int)1e9+7;int maxL= Math.min(arrLen-1,steps/2);int[][] dp = new int[steps + 1][maxL+1];;for (int i=1;i<=steps;i++){for (int j=0;j<=maxL;j++){dp[i][j]=dp[i-1][j];if(j-1>=0)dp[i][j]=(dp[i][j]+dp[i-1][j-1])%m;if(j+1<=maxL) dp[i][j]=(dp[i][j]+dp[i-1][j+1])%m;}}return dp[steps][0];} }

總結(jié)

以上是生活随笔為你收集整理的leetcode 1269. 停在原地的方案数（dp）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。