暴力递归->动态规划->空间压缩

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

//首先看到题目，可变参数只有两个 i和k;所以需要二维dp数组来表示其最优解；
//但是最优解的过程往往是通过子问题的最优解递推得出，所以找出特殊位置初始化很重要；
//但是往往动态规划问题都可以使用递归解决，既然存在递归那么必然存在状态转换式，而且递归的终止条件
//便是我们的特殊位置；
//有了初始条件和状态转换式问题就迎刃而解；
//dp[rest][cur] 表示在当前位置上还剩余多少步；
//当dp[0][p] = 1 因为个时候满足条件，前面的尝试有效；
//由状态转换式可以出本题只需要一维数组就可以实现；故采用空间压缩；

int main(){

    int N,M,K,P;
    int mod = 1000000007;
    while(cin >> N >> M >> K >> P){
        //vector<vector<int>> dp(K + 1,vector<int>(N + 1,0));
        vector<int> dp(N + 1,0);
        dp[P] = 1;
        for(int i = 1; i <= K; ++i){
            //代表左上角的值
            int leftup = dp[1];
            for(int j = 1; j <= N; ++j){
                //如果cur = 1,说明此时只能向右走一步,此时位置为2；
                //此时必须将当前的dp[j]保存，因为我们后边的值要依赖上一行的值；
                int tmp = dp[j];
                if(j == 1){
                    //此时dp[j + 1]还是上一行的值
                    dp[j] = dp[j + 1]%mod;
                }else if(j == N){
                    //如果cur = N,说明此时只能向左走一步，此时位置为 N-1;
                    //此时需要的上一行左边的值所以我们已经保存了它；
                    dp[j] = leftup%mod;
                }else{
                    //此时cur处于普遍位置，既可以向左也可以向右
                    //j + 1的位置直接就是上一行的值，leftup就是上一行左边的值
                    dp[j] = (dp[j + 1] + leftup)%mod;
                }
                leftup = tmp;
            }
        }
        cout << dp[M]%mod << endl;
    }
    return 0;
}