一题学会高维动态规划——”生日快乐“

当多个类型的动态规划模型结合在一起后。动态规划的维度就会叠加。虽然这类题目难度并没有增加很多，但我们需要花费更多耐心，防止其中的环节出现问题。

我们来看一个从左上角到右下角，只能够向右或向下走类的动态规划和01背包相结合的问题：

今天是蒜头君的生日，妈妈带蒜头君到 蛋糕花园 挑选爱吃的蛋糕。蛋糕花园 花园是一个 n 行 m 列的网格图。第 i 行第 j 列格子上放有w[i][j] 克的蛋糕。蒜头君从左上角走到右下角，只能够向右或向下走。当蒜头君走到这个方格时，他可以选择将这个方格上的蛋糕全部吃掉，或是一口都不吃。虽然蒜头君很爱吃蛋糕，但是毕竟他的胃口是有限的，他最多能吃 K 克蛋糕。蒜头君想要知道他在从左上角到右下角的过程中，最多能吃多少蛋糕呢？（蒜头君不能吃蛋糕超过他的胃口大小！）
其中1≤n,m,K≤100， 1≤w[i][j] ≤100。

我们定义状态为dp[i][j][k]，i表示现在在第几行，j表示在第几列，k表示目前吃掉了几个蛋糕。
如果这一步是dp[i][j][k]，那么首先需要考虑位置i-1,j和i,j-1与k（不吃）和k-1（吃）
我们可以列出状态转移方程为：
dp[i][j][k]=dp[i-1][j][k-w[i][j]] || dp[i][j-1][k-w[i][j]] || dp[i-1][j][k] || dp[i][j-1][k]
在做动态规划问题时千万不要遗漏边界条件，对于本题目种的状态定义，很明显当k=0时，任意的dp[i][j][0]=1，而对于其他k≠0的状态，很明显这些状态都不能取到，故当k≠0，dp[i][j][k]=0

或者也有另一种解法（听着就很头大的背包），但是没有必要。
我们定义状态dp[i][j][k]为在第i行第j列上背包体积为k的最大价值，并把每块蛋糕的体积看作w[i][j]，价值为w[i][j]的物品。这样我们要求的就是在第n行第n列上背包体积不超过为K的最大价值，状态转移方程是:
dp][i][j][k]=max(dp[i-1][j][k-w[i][j]],dp[i][j–1][k-w[i][j]]+w[i][j],dp[i-1][j][k],dp[i][j-1][k])
这样也可以把这个高维动态规划模型转化成我们熟悉的形式。

#include 
#include 
using namespace std;
const int N = 105;
bool dp[N][N][N];
int w[N][N];
int main()
{
    int n, m, K;
    cin >> n >> m >> K;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> w[i][j];
        }
    }
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= m; j++){
            dp[i][j][0]=1;
        }
    }
    for(int i = 1;i <= n; i++){
        for(int j = 1; j <= m; j++){
            for(int k = 1; k <= K; k++){
                dp[i][j][k]=dp[i-1][j][k] || dp[i][j-1][k];
                if(k >= w[i][j]){
                    dp[i][j][k] |= dp[i-1][j][k-w[i][j]] || dp[i][j-1][k-w[i][j]];
                }
            }
        }
    }
    for(int i = K; i >= 0; i--){
        if(dp[n][m][i]){
            cout << i << endl;
            break;
        }
    }
    return 0;
}