D Palace

链接：https://ac.nowcoder.com/acm/contest/23942/D 来源：牛客网

题目描述

在一个 n×m 大小的宫殿里面，每个坐标点 (i,j)(i∈[1,n],j∈[1,m]) 处都有一件价值为 w 的物品。

现在小明站在起点 (1,1) 位置，他想走到目标点 (n,m) 处，规定小明每次只能向下或者向右移动（不限移动次数）。

问：小明从起点移动到目标点时总共可以拿走最多多少价值的物品，并输出该价值的大小。

输入描述:

第1行输入两个正整数n和m，表示宫殿的大小(1≤n,m≤100)。
第2-n+1行每行输入m个正整数wij(1≤i≤n,1≤j≤m)，
输入数据之间用空格隔开，wij表示坐标(i,j)处的物品价值 (1≤wij≤10^4)

输出描述:

 输出答案。

示例 1

输入

 3 2
 8 18 
 18 2 
 7 7

输出

 40

这本是一道 dp 模板题，没什么难度，之所以记录下来的原因是我当初做这题的时候，意外的没有想到用 dp，而是深搜，结果可以预料，Time Limit Exceeded

DP 思路

题目限定了只能向右或向下移动，那我只需要设计一个双层循环结构，并定义一个 dp 数组用来保存走到当前位置时的最大价值，然后在代码的最后输出终点对应的 dp 值，就是该题的答案了。

这么说了，表现得思路还是有点模糊，那尝试通过解析代码来进一步了解 dp 的解题思路。

DP 代码

#include <iostream>
#include <cstdio>
using namespace std;
unsigned int map[105][105];
unsigned int dp[105][105];
unsigned int m,n;
​
​
int main()
{
    cin >> n >> m;
    for(unsigned int i = 1; i <= n; i++)
    {
        for(unsigned int j = 1; j <= m; j++)
        {
            cin >> map[j][i];
        }
    }
        for(unsigned int y = 1; y <= n; y++)
    {
        for(unsigned int x = 1; x <= m; x++)
        {
            dp[x][y] = max(dp[x-1][y],dp[x][y-1]) + map[x][y];
        }
    }
    cout << dp[m][n] << endl;
    return 0;
}

				

					
				
				

					
				
				

					
				
				

					
				
			

其实关键部分只有这一个循环语句块

for(unsigned int y = 1; y <= n; y++)
{
    for(unsigned int x = 1; x <= m; x++)
    {
        dp[x][y] = max(dp[x-1][y],dp[x][y-1]) + map[x][y];
    }
}

				

					
				
				

					
				
				

					
				
				

					
				
			

循环遍历了 map，并将当前的 map 值与上一步（左边或上边）的 dp 最大值作和，并将和保存在 dp 中，表示从起点开始走到当前坐标的最大价值和。(dp 初值都为 0)

输出调试

sepline 下面的是 dp 数组的值

其次是答案，通过数据，应该可以清晰地了解 dp 数组的作用。

 3 2
 8 18
 18 2
 7 7
 ---Sep Line---
 8 26
 26 28
 33 40
 40

 3 3
 18 3 18
 18 0 18
 3 0 18
 ---Sep Line---
 18 21 39
 36 36 57
 39 39 75
 75

TLE 代码

#include <iostream>
#include <cstdio>
#include <array>
#include <string>
using namespace std;
unsigned int map[101][101];
unsigned int m,n;
unsigned int ans;
 
void dfs(unsigned int x, unsigned int y,unsigned int temp)
{
    temp+=map[x][y];
    if(y==n&&x==m){
        if(temp > ans) ans = temp;
        return;
    }
    if(y!=n)
    {
        dfs(x,y+1,temp);
    }
    if(x!=m)
    {     
        dfs(x+1,y,temp);
    }
 
}
 
int main()
{
    cin >> n >> m;
    for(unsigned int i = 1; i <= n; i++)
    {
        for(unsigned int j = 1; j <= m; j++)
        {
            cin >> map[j][i];
        }
    }
    dfs(1,1,0);
    cout << ans << endl;
    return 0;
}

				

					
				
				

					
				
				

					
				
				

					
				
			

原因分析：

当 m,n 变大时，dfs 递归就会反复走旧路线重新求和，影响效率，从而导致超时。

解决方法是使用记忆化搜索，减去一些不符号要求的路线，但是这样反而使得算法变得复杂，本题还是使用 dp 来求解。