[LeetCode] 1269. Number of Ways to Stay in the Same Place After Some Steps

https://leetcode.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps/description/

Number of Ways to Stay in the Same Place After Some Steps - LeetCode

문제 유형 : 다이나믹 프로그래밍(탑 다운 메모이제이션) / 재귀

문제 난이도 : Hard

 

문제

You have a pointer at index 0 in an array of size arrLen. At each step, you can move 1 position to the left, 1 position to the right in the array, or stay in the same place (The pointer should not be placed outside the array at any time).

Given two integers steps and arrLen, return the number of ways such that your pointer is still at index 0 after exactly steps steps. Since the answer may be too large, return it modulo 10^9 + 7.

 

arrLen만큼의 크기를 가진 배열의 0번째 인덱스에 있습니다. 당신은 왼쪽, 오른쪽, 머무름의 행동을 할 수 있습니다.

당신은 배열 범위 밖으로 벗어날 수 없습니다. 모든 행동 횟수 step번을 한 후에 다시 0번째 인덱스에 있어야 합니다.

 

이 경우의 수를 구하시오. 값이 커질 수 있으므로, 1e9+7로 나눈 나머지를 반환하시오.

 

풀이

탑 다운 재귀 방식으로 풀 수 있다.

지금 위치에서 왼쪽으로 이동한 경우의 수, 오른쪽으로 이동한 경우의 수, 머물렀을 때의 경우의 수들을 재귀적으로 누적시켜준다.

범위의 밖을 나간 경우나, 남은 이동의 수가 0이고 인덱스가 0인 경우 등의 작은 케이스들의 처리도 해주면 된다.

 

코드

C++

const int MOD = 1e9+7;

class Solution {
public:
    int numWays(int steps, int arrLen) {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);

        int maxLen = min(steps, arrLen);
        
        vector<vector<int>> dp(steps+1, vector<int>(maxLen, -1));
        
        return solve(steps, maxLen, 0, dp);
    }

    int solve(int leftSteps, int maxLen, int index, vector<vector<int>> &dp) {
    	// 남은 행동의 개수가 0인데, 인덱스도 0이면 경우의 수 하나 추가
        if (leftSteps == 0) return (index == 0) ? 1 : 0;
        // 범위를 벗어나면 제외
        if (index < 0 || index >= maxLen) return 0;
        // 값이 있으면 반환
        if (dp[leftSteps][index] != -1) return dp[leftSteps][index];

		// 오른쪽, 왼쪽, 가만히 있을 때의 경우의 수들을 재귀적으로 계산
        int rightMove = solve(leftSteps - 1, maxLen, index + 1, dp) % MOD;
        int leftMove = solve(leftSteps - 1, maxLen, index - 1, dp) % MOD;
        int stayMove = solve(leftSteps - 1, maxLen, index, dp) % MOD;
		
        // 경우의 수들 누적 후 저장
        dp[leftSteps][index] =((rightMove + leftMove)%MOD+ stayMove) % MOD;

        return dp[leftSteps][index];
    }
};

 

Swift

let MOD = 1_000_000_007

class Solution {
    var dp = [[Int]]()
    
    func numWays(_ steps: Int, _ arrLen: Int) -> Int {
        let maxLen = min(steps, arrLen)
        dp = Array(repeating: Array(repeating: -1, count: maxLen), count: steps + 1)
        return solve(steps, maxLen, 0)
    }
    
    func solve(_ leftSteps: Int, _ maxLen: Int, _ index: Int) -> Int {
        if leftSteps == 0 {
            return index == 0 ? 1 : 0
        }
        
        if index < 0 || index >= maxLen {
            return 0
        }
        
        if dp[leftSteps][index] != -1 {
            return dp[leftSteps][index]
        }
        
        var rightMove = solve(leftSteps - 1, maxLen, index + 1) % MOD
        var leftMove = solve(leftSteps - 1, maxLen, index - 1) % MOD
        var stayMove = solve(leftSteps - 1, maxLen, index) % MOD
        
        dp[leftSteps][index] = (rightMove + leftMove + stayMove) % MOD
        
        return dp[leftSteps][index]
    }
}

 

dart

const int MOD = 1000000007;

class Solution {
  List<List<int>> dp = [];

  int numWays(int steps, int arrLen) {
    int maxLen = steps < arrLen ? steps : arrLen;
    dp = List.generate(steps + 1, (i) => List<int>.filled(maxLen, -1));
    return solve(steps, maxLen, 0);
  }

  int solve(int leftSteps, int maxLen, int index) {
    if (leftSteps == 0) {
      return index == 0 ? 1 : 0;
    }

    if (index < 0 || index >= maxLen) {
      return 0;
    }

    if (dp[leftSteps][index] != -1) {
      return dp[leftSteps][index];
    }

    int rightMove = solve(leftSteps - 1, maxLen, index + 1) % MOD;
    int leftMove = solve(leftSteps - 1, maxLen, index - 1) % MOD;
    int stayMove = solve(leftSteps - 1, maxLen, index) % MOD;

    dp[leftSteps][index] = (rightMove + leftMove + stayMove) % MOD;

    return dp[leftSteps][index];
  }
}