动态规划（从集合角度思考）

解题思路:动态规划（从集合角度思考）

注意事项:弄清状态表示与状态计算 这里分成两大类：（1）最后一步是从上往下走 （2）最后一步是从左往右走

两大类再细分取与不取  故写成四种状态 ：

f[i-1,j,k,c]  f[i,j-1,k,c] f[i-1,j,k-1,c] f[i,j-1,k-1,c'] 其中c'<c

 

参考代码:

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N = 55, MOD=1000000007;
int f[N][N][13][14];
int w[N][N];
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>>w[i][j];
            w[i][j]++;
        }
    
    f[1][1][1][w[1][1]]=1;
    f[1][1][0][0]=1;
    
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(i==1&&j==1) continue;
            for(int u=0;u<=k;u++)
                for(int v=0;v<=13;v++)
                {
                    int &val=f[i][j][u][v];
                    val=(val+f[i-1][j][u][v])%MOD;
                    val=(val+f[i][j-1][u][v])%MOD;
                    if(u>0&&v==w[i][j])
                    {
                        for(int c=0;c<v;c++)
                        {
                            val=(val+f[i-1][j][u-1][c])%MOD;
                            val=(val+f[i][j-1][u-1][c])%MOD;
                        }
                    }
                }
        }

    
    int res=0;
    for(int i=0;i<=13;i++) res=(res+f[n][m][k][i])%MOD;
    
    cout << res << endl;
    return 0;
}