LeetCode 1269. 停在原地的方案数动态规划

墨蓝 2023-01-21 02:13 5阅读 0赞

*  有一个长度为 arrLen 的数组，开始有一个指针在索引 0 处。
 *  每一步操作中，你可以将指针向左或向右移动 1 步，或者停在原地（指针不能被移动到数组范围外）。
 *  给你两个整数 steps 和 arrLen ，请你计算并返回：在恰好执行 steps 次操作以后，指针仍然指向索引 0 处的方案数。
 *  由于答案可能会很大，请返回方案数 模 10^9 + 7 后的结果。

示例 1：
    
    输入：steps = 3, arrLen = 2
    输出：4
    解释：3 步后，总共有 4 种不同的方法可以停在索引 0 处。
    向右，向左，不动
    不动，向右，向左
    向右，不动，向左
    不动，不动，不动
    示例  2：
    
    输入：steps = 2, arrLen = 4
    输出：2
    解释：2 步后，总共有 2 种不同的方法可以停在索引 0 处。
    向右，向左
    不动，不动
    示例 3：
    
    输入：steps = 4, arrLen = 2
    输出：8
     
    
    提示：
    
    1 <= steps <= 500
    1 <= arrLen <= 10^6
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
        
        public int numWays(int steps, int arrLen) {
        
            int mod=1000000007;
            int range=Math.min(steps, arrLen-1);//位置不超过数组范围
            int dp[][]=new int[steps+1][range+1];//第i步位于第j个位置的方案数
            dp[0][0]=1;//初始值
            for(int i=1;i<=steps;i++) {
        
            	for(int j=0;j<=range;j++) {
        
            		dp[i][j]=dp[i-1][j];//不动的情况
            		if(j>0) {
        
            			dp[i][j]=(dp[i][j]+dp[i-1][j-1])%mod;//右移的情况
            		}
            		if(j<range) {
        
            			dp[i][j]=(dp[i][j]+dp[i-1][j+1])%mod;//左移的情况
            		}
            	}
            }
            return dp[steps][0];
        }
    }