Số cách ở lại vị trí ban đầu sau một số bước trong C++

Cho mảng kích thước arrLen, con trỏ tại chỉ số 0. Mỗi bước: trái, phải, hoặc ở yên. Cho steps và arrLen, tìm số cách con trỏ vẫn ở chỉ số 0 sau đúng steps bước. Modulo 1e9+7.

Ví dụ: steps=3, arrLen=2 → 4. Các cách: [Right,Left,Stay], [Stay,Right,Left], [Right,Stay,Left], [Stay,Stay,Stay].

Giải pháp

DPbottom-up với tối ưu không gian (rolling array):

• Chỉ cần xét vị trí đến min(arrLen, steps/2+1) (không thể đi xa hơn steps/2)
• dp[2][x+1]: dp[y][j] = số cách ở vị trí j sau i bước
• Khởi tạo: dp[0][0] = 1
• Duyệt i từ 1 đến steps:
  • x = (i-1)%2, y = i%2
  • dp[y][j] = dp[x][j] (ở yên)
  • Nếu j>0: dp[y][j] += dp[x][j-1] (từ trái)
  • Nếu j+1
  • Modulo 1e9+7
• Trả về dp[steps%2][0]

Ví dụ mã C++

#include <bits/stdc++.h> 
using namespace std; 

typedef long long int lli; 
const int MOD = 1e9 + 7; 

lli add(lli a, lli b) { 
    return (a % MOD + b % MOD) % MOD; 
} 

class Solution { 
public: 
    vector<vector<int> > dp; 
    
    int solve(int n, int x, int pos = 0) { 
        if (x == 0) return pos == 0; 
        if (dp[pos][n] != -1) return dp[pos][n]; 
        int ans = 0; 
        if (pos > 0) ans = add(ans, solve(n, x-1, pos-1)); 
        if (pos < n-1) ans = add(ans, solve(n, x-1, pos+1)); 
        ans = add(ans, solve(n, x-1, pos)); 
        dp[pos][n] = ans; 
        return ans; 
    } 
    
    int numWays(int steps, int arrLen) { 
        int x = min(arrLen, steps / 2 + 1); 
        this->dp = vector<vector<int> >(2, vector<int>(x + 1, 0)); 
        dp[0][0] = 1; 
        int n = arrLen; 
        
        for (int i = 1; i <= steps; i++) { 
            for (int j = 0; j < min(arrLen, steps / 2 + 1); j++) { 
                int x = (i - 1) % 2; 
                int y = i % 2; 
                dp[y][j] = dp[x][j]; 
                if (j - 1 >= 0) dp[y][j] = add(dp[y][j], dp[x][j-1]); 
                if (j + 1 < n) dp[y][j] = add(dp[y][j], dp[x][j+1]); 
            } 
        } 
        return dp[steps % 2][0]; 
    } 
}; 

int main() { 
    Solution ob; 
    cout << (ob.numWays(3,2)); 
    return 0; 
}

Đầu vào

3, 2

Đầu ra

4