C++ 地宫取宝 DP

解题思路:看了一眼数据这么小想到可以利用DP解决 想出dp表达式idp[i][j][t][c];//坐标为 i j 最大价值为t 身上宝物为c时候的状态数量 分两种情况转移 1.没选当前格子的 2.能够选当前格子的

注意事项:记得开long long

参考代码:

#include<bits/stdc++.h>

#define int long long

#define MO 1000000007

using namespace std;

int dp[55][55][15][15];//坐标为 i j 最大价值为t 身上宝物为c时候的状态数量

int n,m,k,ma[55][55];

signed main()

{   

    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin>>n>>m>>k;

    for(int i=1;i<=n;i++){

        for(int j=1;j<=m;j++){

            cin>>ma[i][j];

            ma[i][j];

            ma[i][j]++;

        }

    }

    dp[1][1][ma[1][1]][1]=dp[1][1][0][0]=1;

    for(int i=1;i<=n;i++){

        for(int j=1;j<=m;j++){

            for(int t=0;t<=12;t++){

                for(int c=0;c<=k;c++){

                    //先不选

                    dp[i][j][t][c]=(dp[i][j][t][c]+dp[i-1][j][t][c]+dp[i][j-1][t][c])%MO;

                    //如果能选

                    if((ma[i][j])==t&&c>0){

                        //记得包括多种情况

                        for(int temp=0;temp<t;temp++){

                            dp[i][j][t][c]=(dp[i][j][t][c]+dp[i-1][j][temp][c-1])%MO;

                            dp[i][j][t][c]=(dp[i][j][t][c]+dp[i][j-1][temp][c-1])%MO;

                        }

                    }

                }

            }

        }

    }

    int ans=0;

    for(int i=0;i<15;i++){ans+=dp[n][m][i][k];ans%=MO;}

    cout<<ans<<endl;

}