Project Euler_Problem 178_Step Numbers_动态规划

原题目：

解题思路：动态规划

代码：

ll R[50][11][2048];

void solve() {
    ll i, j,k,x,y,z,p,q,u,v;
    N = 40, NN = 1024;
    //N = 20;
    double a, b, c,d;
    

    for (i = 0; i <= 9; i++) {
        R[1][i][1 << i] = 1;
    }



    for (i = 2; i <= N; i++) {
        for (j = 0; j <= 9 ; j++) {
            for (k = 0; k < 1024; k++) {
                if (j - 1 >= 0) {
                    R[i][j][k | (1 << j)] += R[i - 1][j - 1][k];
                }
                if (j + 1 <= 9) {
                    R[i][j][k | (1 << j)] += R[i - 1][j + 1][k];
                }
            }

            if (j != 0) {
                ans1 = ans1 + R[i][j][1023];
            }
        }
    }


    printf("%lld\n",ans1);
}