힘: 1269 제자리에 머무르는 방안 수

class Solution {
public:
    int ans = 0;

    void dfs(int steps, int direction, int arrLen){
        if(steps == 0)
        {
            if(direction == 0)
                ans++;
            else
                return;
        }
        else
        {
            if(arrLen > 1 + direction)
                dfs(steps - 1, direction + 1, arrLen);
            if(0 <= direction - 1)
                dfs(steps - 1, direction - 1, arrLen);
            dfs(steps - 1, direction, arrLen);
        }
    }

    int numWays(int steps, int arrLen) {
        dfs(steps, 0, arrLen);
        return ans;
    }
};

class Solution {
public:

    const int mod = 1e9+7;

    int numWays(int steps, int arrLen) {
        int ans = 0;

        //steps arrLen ，  dp 
        arrLen = min(steps, arrLen);
        vector>dp(steps + 1, vector(arrLen, 0));

        //dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] + dp[i][j + 1]
        // ， 
        // 

        dp[0][0] = 1;
        for (int i = 1; i <= steps; ++i) {
            for (int j = 0; j < arrLen; ++j) {
                for (int k = -1; k <= 1; ++k) {
                    // ， 
                    if (j - k >= 0 && j - k < arrLen) {
                        dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % mod;
                    }
                }
            }
        }
        for(int i = 0; i < steps + 1; ++i)
        {
            for(int j = 0; j < arrLen; ++j)
            {
                cout << dp[i][j] << " ";
            }
            cout << endl;
        }
        return dp[steps][0];
    }
};

// steps = 4, arrLen = 2  ， 5 2