标准C语言满分题解！！！

解题思路:

注意事项:

为什么是四维？

因为里面有坐标i,j从两个方向来，还有k件物品需要维护，另外还有最后一件物品的价值c需要维护，因为需要c来比较，是否取不取，这样就可以表示出，这个问题了。

参考代码:

#include <stdio.h>

int dp[51][51][15][15];//dp[i][j][k][v]表示走到坐标为[i,j],取了k个数,最后一个物品的价值是v的方案数

int c[51][51];  //输入得n*m矩阵

int main()

{

    int i,j,u,l;

    int n,m,k;

    scanf("%d%d%d",&n,&m,&k); //输入

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

    {

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

        {

            scanf("%d",&c[i][j]);

        }

    }

    dp[1][1][0][-1]=1; //不取左上角 边界赋值 避免无法取到价值为0的物品 将最后一个参数置为-1

    dp[1][1][1][c[1][1]]=1;//取左上角

    for(i=1;i<=n;i++) //遍历矩阵

    {

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

        {

            if(i==1&&j==1)

            {

                continue;

            }

            for(u=0;u<=k;u++) //枚举所有方案数 选了u个物品

            {

                for(l=-1;l<=12;l++) //枚举最后一个物品的价值(最大价值)

                {

                    //不取(i,j)位置上的物品

                    int *num=&dp[i][j][u][l];

                    (*num)=((*num)+dp[i-1][j][u][l])%1000000007; //从上方下来

                    (*num)=((*num)+dp[i][j-1][u][l])%1000000007; //从左边过来

                    //取(i,j)位置上的物品

                    if(u>0&&c[i][j]==l)  //枚举取当前[i,j]位置上的物品 当前物品的价值必须等于l

                    {

                        for(int w=-1;w<l;w++)  //枚举上一个方案中小于最后一个物品价值的所有可能

                        {

                            (*num)=((*num)+dp[i-1][j][u-1][w])%1000000007;

                            (*num)=((*num)+dp[i][j-1][u-1][w])%1000000007;

                        }

                    }

                }

            }

        }

    }

    int num=0;

    for(i=-1;i<=12;i++)

    {

        num=(num+dp[n][m][k][i])%1000000007;

    }

    printf("%d",num);

    return 0;

}