hihocoder1037（记忆化搜索）

题目连接：点击打开链接

解题思路：

和白书上的数字三角形一样，，用记忆化搜索解决，推出转移方程dp[i][j] = g[i][j] + max( d( i + 1 , j ) , d( i + 1 , j + 1) );

完整代码：

#include <iostream>#include <cstdio>#include <cstring>#include <climits>using namespace std;const int maxn = 1111;int g[maxn][maxn];int dp[maxn][maxn];int n;int d(int i , int j){if(dp[i][j] > 0) return dp[i][j];return dp[i][j] = g[i][j] + (i == n ? 0 : max(d(i + 1 , j) , d(i + 1 , j + 1)));}int main(){#ifdef DoubleQfreopen("in.txt" , "r" , stdin);#endifwhile(cin >> n){memset(g , 0 , sizeof(g));memset(dp , -1 , sizeof(dp));for(int i = 1 ; i <= n ; i ++){for(int j = 1 ; j <= i ; j ++){cin >> g[i][j];}}cout << d(1 , 1) << endl;}}

怠惰是贫穷的制造厂。