对“地宫取宝 （C++代码）--正确AC解法是动态规划,6ms通过”的详细解释和修正

解题思路:

这篇题解要配合“地宫取宝 （C++代码）--正确AC解法是动态规划,6ms通过”的大佬帖子一起服用。

我做出了如下调整

1. 用C语言重写

2. 去掉了大佬for的宏，使代码易于阅读

3. 将12改成了13，我认为大佬这里存在错误，因为“大于”要求比最大的宝物价值（12）还要大，所以应该是13

4. 给变量取了更加易懂的名称

5. 用注释的方法对大佬的思路进行了进一步解释

6. 注释中含有两个打印语句，可以用来观察dp数组的生成，理解自底向顶的动态规划，与自顶向底的记忆DFS对比
   

注意事项:

参考代码:

#include<stdio.h>

#include<math.h>

#include<ctype.h>

#include<string.h>

#include<stdlib.h>

#include<time.h>

#include<assert.h>

#define mod 1000000007

int board[51][51];

int n;

int m;

int k;

int dp[51][51][15][15];

//从底向顶的动态规划 

//dp 的四个下标代表，坐标；拿了num个物品；这些物品的最大价值小于MaxValue（不一定是上确界，只是上界）的方案总数 

void DpMaker()

{

    int x,y,num,MaxValue;

    long long na,buna;

    //四重循环，顺序不能调，因为有递归关系 

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

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

            for(num=0; num<=k; num++)

                //13是物品最大价值是12 

                for(MaxValue=0; MaxValue<=13; MaxValue++)

                 {

                      na=buna=0;

                     if(x == 1 && y == 1)

                     {

                     //什么都没拿也是一种方案 

                           if(num == 0 || (num == 1 && MaxValue>board[x][y]))

                              {

                                 dp[x][y][num][MaxValue]=1;

                              }

                              //printf("dp[%d][%d][%d][%d]=%d\n",x,y,num,MaxValue,dp[x][y][num][MaxValue]);

                          continue;

                      }

                      //对应在这个坐标下要拿东西了 ，因为要拿东西，所以num至少是1，只有在小于上界的时候才能拿 

                     if(num>0 && MaxValue>board[x][y])

                     {

                         na=dp[x-1][y][num-1][board[x][y]]+dp[x][y-1][num-1][board[x][y]];

                     }

                     buna=dp[x-1][y][num][MaxValue]+dp[x][y-1][num][MaxValue];

                      dp[x][y][num][MaxValue]=(na+buna)%mod;

                      //printf("dp[%d][%d][%d][%d]=%d\n",x,y,num,MaxValue,dp[x][y][num][MaxValue]);

                 }

               }

int main(){

int i,j;

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

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

{

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

    {

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

    }

}

DpMaker();

//答案对物品价值没有要求，所以取13 

printf("%d",dp[n][m][k][13]);

return 0;

}