主要思路
首先明确几个限制:
- 只能向下或向右移动
- 单调递增的进行选择
- 总共能取k件物品
动态规划
- 状态表示:
f[i,j,k,c]
- 集合:从起点走到$(i,j)$, 且恰好已经取了k件物品,且最后一件物品的价值是
C
的 合法方案的集合 - 属性:数量,所有满足条件的方案数
- 集合:从起点走到$(i,j)$, 且恰好已经取了k件物品,且最后一件物品的价值是
- 状态计算
划分子集:寻找最后一个不同点 - 所有最后一步是从上向下的走法:上一步, c’ 表示上一步取的价值,当前的价值是c
- 不取当前情况:
f[i-1,j,k,c]
- 取当前情况: 满足
w[i][j]==c
条件:f[i-1,j,k-1,c']
, 且 c’<c
- 不取当前情况:
- 所有最后一步是从左向右的走法:上一步, c’ 表示上一步取的价值,当前的价值是c
- 不取当前情况:
f[i,j-1,k,c]
- 取当前情况: 满足
w[i][j]==c
条件:f[i,j-1,k-1,c']
, 且 c’<c
- 不取当前情况:
dp数组的初始化:
- 取该第一个物品:
dp[1][1][1][w[1][1]]=1;
- 不取第一个物品:
dp[1][1][0][0]=1
代码
#include <iostream>
using namespace std;
const int N=55;
const int MOD=1000000007;
int n,m,k;
int w[N][N];
int dp[N][N][13][14]; //dp[i][j] 表示走过i行 j列,最多取13(1~12)件物品,价值最大14(-1~12) 有dp[i][j] 中不同的方案
int main()
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>w[i][j];
//将所有的价值增加一个,这样在初始时如果不取任何物品的价值就是0
w[i][j]++;
}
}
//dp数组的初始化
dp[1][1][1][w[1][1]]=1; //取第1件物品
dp[1][1][0][0]=1; //不取第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++) //宝贝的数量,从0开始
{
for(int v=0;v<=13;v++) //价值由于自增过了,如果不选该物品,没有价值就是0
{
//方便书写
int &val=dp[i][j][u][v];
//不取
val=(val+dp[i-1][j][u][v])%MOD; //从上到下
val=(val+dp[i][j-1][u][v])%MOD; //从左到右
//取物品
if(u>0&&v==w[i][j]) //价值必须是当前的价值才能取
{
for(int c=0;c<v;c++) //价值
{
val=(val+dp[i-1][j][u-1][c])%MOD; //由于取模的数字很大,所以最多是两个数相加,否则就会超过 int 范围了
val=(val+dp[i][j-1][u-1][c])%MOD;
}
}
}
}
}
}
int res=0;
for(int i=0;i<=13;i++)
{
//所有的方案数
res=(res+dp[n][m][k][i])%MOD;
}
cout<<res<<"\n";
return 0;
}