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

• Recursive 방식으로 풀어보려고 했는데 time exceeded로 실패.

• 먼저 제약 조건에 대한 부분.
• position 0으로 돌아오려면 left, right step의 숫자는 같아야 한다.
• 따라서 최대 이동 가능한 위치 maxPos 는 step / 2 또는 array 끝 부분 arrLen - 1에 해당된다.

• DP의 점화식은 아래와 같다.
• 현재 위치를 i, step 수를 s 라고 할 때
• 현재 위치 i 에서 stay 하는 경우 dp[i][s - 1]
• 이전 위치 i - 1 에서 오른쪽으로 이동한 경우 dp[i - 1][s - 1] (단, i > 0)
• 다음 위치에서 왼쪽으로 이동한 경우 dp[i + 1][s - 1] (단, i ≤ maxPos)

• 점화식에서 이전 step 숫자의 값들을 참조하므로 outer loop는 step 수, inner loop는 위치로 한다.

class Solution {
public:
    static constexpr int MOD = 1e9 + 7;
    int numWays(int steps, int arrLen) {
        int maxPos = min(steps / 2, arrLen - 1);
        vector<vector<int>> dp(maxPos + 1, vector<int>(steps + 1, 0));
        dp[0][0] = 1;
        for (int s = 1; s <= steps; ++s) {
            for (int i = 0; i <= maxPos; ++i) {
                int value = dp[i][s - 1];
                if (i > 0) {
                    value = (value + dp[i - 1][s - 1]) % MOD;
                }
                if (i < maxPos) {
                    value = (value + dp[i + 1][s - 1]) % MOD;
                }
                dp[i][s] = value;
            }
        } 
        return dp[0][steps];
    }
};