超详细通俗易懂C++

     解题思路:1.用四维表示小明每次达到一个位置，此时已经拿到的宝贝数目以及最近获得的宝贝价值，最近获得的可以是当前格子取的，也可以是当前格子不取之前宝贝的价值；用四维的原因是，我们不仅要记录小明所在格子位置，还要记录他现在有几个宝贝，这样才能判断到底能否再终点达到恰好k个，还要记录小明现在拿的宝贝最大价值多少，进行价值不同各种方案的相加。也就是k,c表示的值是我们都要一直维护的，所以要用四维。

        2.在这个代码中，只分为拿和不拿，要是拿，那么只有一种情况->当前格子的宝贝价值一定大于小明现在拥有的宝贝的，这样就排除了当前格子宝贝价值大于小明已有的，纠结是拿是不拿的问题。

        3.在拿和不拿的情况中都有两种情况，分别是从左边来的和从上面来的，因为小明只能右走和下走，分这种情况是因为我们代码中要用之前格子的方案数目来获得现在格子的方案数目，所以要追溯来路。

        4.四维 f[i][j][k][c]表示当前（i，j）位置格子小明已经拥有的宝贝数目k,以及最近获得宝贝价值，注意若当前格子获取宝贝，那么c就是当前格子的，若不获取，就是之前的。

            (1)在(i,j)位置不取，从左边来，之前位置的c就为当前位置的c,上面来的同理

f[i][j-1][k][c]

           （2）在(i,j)位置不取当前格子宝贝，从上面来：

f[i-1][j][k][c]

            (3)在(i,j)位置获取当前格子的宝贝，从左面来，t为之前位置的c,只不过这里t<c,因为要满足取的宝贝价值一定大于之前拥有宝贝的，小于c时t有多种i情况，而不取时只有c一种情况，所以当取时，要把所有t的情况都枚举加起来

f[i][j-1][k-1][t]

            (4)在(i,j)位置取宝贝，从上面来：

f[i-1][j][k-1][t]

t要多种情况枚举：

if(k>0&&C[i][j]==c){
                        for(int t=0;t<C[i][j];t++){
                            f[i][j][k][c]=((f[i][j][k][c]+f[i-1][j][k-1][t])%mod+f[i][j-1][k-1][t])%mod;
                        }
                    }

        5.给f[i][j][k][c]的起点初始化对应方案数目，其他值默认初值为0，因为(i,j)从（1，1）开始遍历赋值，所以i=0；j=0时边缘化，为0不会影响，其余位置后续会通过循环赋值；

// 取第一个物品
    f[1][1][1][C[1][1]]=1;  
    // 不取第一个物品
    f[1][1][0][0]=1;

由于起点不取第一个物品时，,因为物品价值范围为[0,12],可以取0值，所以物品价值c应为-1，但是不允许-1索引，所以把输入所有宝贝价值统一加一，用0表示-1。

for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>C[i][j];
            // 因为价值有0，所以整体加1，用0表示原来起点不取宝贝c为-1这个数值
            C[i][j]++;
        }
    }

        6.注意f[i][j][k][c]为不取左,上，取左，上四种情况相加的方案数，在最后求终点恰好k个物品的方案数目res时，为f[n][m][k][i]（其中i包含0-13）这些状态的值相加；

注意事项：

1.在取时的判断：k要大于0，因为f[i][j][k][c]中k为当前状态已经获取的宝贝数目，若c为当前格子取的，那么k一定不为0，不然就与之矛盾

if(k>0&&C[i][j]==c)

2.涉及mod，一般最后结果还要取模

res=(res+f[n][m][K][i])%mod;

参考代码:

#include<iostream>
#include <cstdio>
#include <cmath>
using namespace std;
// 数值随意，满足1<=n,m<=50,1<=k<=12,够用就行
// 价值数组，存储格子内宝贝的价值
int C[55][55];
/* f[i][j][k][c],(i,j)为当前所在格子位置，k为当前位置已经拿到的宝贝数目，c为最近取得的宝贝的价值*/
int f[55][55][15][15];
int mod=1000000007;

int n,m,K;
int main()
{
    cin>>n>>m>>K;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>C[i][j];
            // 因为价值有0，所以整体加1，用0表示原来起点不取宝贝c为-1这个数值
            C[i][j]++;
        }
    }
    // 其余默认初值为0
    // 取第一个物品
    f[1][1][1][C[1][1]]=1;  
    // 不取第一个物品
    f[1][1][0][0]=1;
    // (i,j)从1开始搜索，因为后续有i-1防止出现-1索引，并且相对于从0索引更直观
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            for(int k=0;k<=K;k++){
                for(int c=0;c<=13;c++){
                    // 不取的情况包括从左边和从上面来的,
                    f[i][j][k][c]=((f[i][j][k][c]+f[i-1][j][k][c])%mod+f[i][j-1][k][c])%mod;
                    // 取宝贝，要满足k>0且当前位置宝贝价值为c
                    // 从左边和上面来的情况里，小于c的所有情况都加起来
                    if(k>0&&C[i][j]==c){
                        for(int t=0;t<C[i][j];t++){
                            f[i][j][k][c]=((f[i][j][k][c]+f[i-1][j][k-1][t])%mod+f[i][j-1][k-1][t])%mod;
                        }
                    }
                    
                }
            }
        }
    }
    int res=0;
    // 把终点位置恰好获得k个宝贝价值从0-13所有情况加起来
    for(int i=0;i<=13;i++){
        res=(res+f[n][m][K][i])%mod;
    }
    cout<<res;
    return 0;
}