法一:dfs
include[HTML_REMOVED]
using namespace std;
const int N = 510;
int a[N][N];
int n;
bool yn[N][N];
int ans ,sum;
void dfs(int i ,int j)
{
if(i == n)
{
ans = max(ans , sum);
return ;
}
for(int k = 0 ; k <= 1 ; k++)
{
if(!yn[i + 1][j + k])
{
yn[i + 1][j + k] = true;
sum += a[i + 1][j + k];
dfs(i + 1 , j + k);
yn[i + 1][j + k] = false;
sum -= a[i + 1][j + k];
}
}
}
int main()
{
cin >> n;
for(int i = 1; i <= n ; i++)
{
for(int j = 1 ; j <= i ; j++) cin >> a[i][j];
}
dfs(1 , 1);
cout << ans + a[1][1];
return 0;
}
法二:用递归实现
include[HTML_REMOVED]
using namespace std;
const int N = 510;
int a[N][N];
int n;
int f(int i ,int j)
{
if(i == n) return a[i][j];
return max(a[i][j] + f(i + 1 , j) ,a[i][j] + f(i + 1 , j + 1));
}
int main()
{
cin >> n;
for(int i = 1; i <= n ; i++)
{
for(int j = 1 ; j <= i ; j++) cin >> a[i][j];
}
cout << f(1 , 1);
return 0;
}
该方法仍可能超时因为存在大量重复的递归,加入记忆化数组进行优化
include[HTML_REMOVED]
using namespace std;
const int N = 510;
int a[N][N];
int n;
int memo[N][N];
int f(int i ,int j)
{
if(memo[i][j] != 0) return memo[i][j];
if(i == n) return a[i][j];
memo[i][j] = max(a[i][j] + f(i + 1 , j) ,a[i][j] + f(i + 1 , j + 1));
return memo[i][j];
}
int main()
{
cin >> n;
for(int i = 1; i <= n ; i++)
{
for(int j = 1 ; j <= i ; j++) cin >> a[i][j];
}
cout << f(1 , 1);
return 0;
}
法三:dp,用数组模拟递归的过程
include[HTML_REMOVED]
using namespace std;
const int N = 510;
int a[N][N];
int n;
int ans[N][N];
int main()
{
cin >> n;
for(int i = 1; i <= n ; i++)
{
for(int j = 1 ; j <= i ; j++) cin >> a[i][j];
}
for(int i = n ; i >= 1 ; i--)
{
for(int j = i ; >= 1 ; j--)
{
if(i == n) ans[i][j] = a[i][j];//把最后一行ans初始化
else
{
ans[i][j] = a[i][j] + max(ans[i][j] , ans[i][j + 1]);
}
}
}
cout << ans[1][1];
return 0;
}
通过观察发现可以压缩成一维数组
include[HTML_REMOVED]
using namespace std;
const int N = 510;
int a[N][N];
int n;
int ans[N];
int main()
{
cin >> n;
for(int i = 1; i <= n ; i++)
{
for(int j = 1 ; j <= i ; j++) cin >> a[i][j];
}
for(int i = n ; i >= 1 ; i--)
{
for(int j = 1 ; j <= i ; j++)//顺序更新 ans
{
if(i == n) ans[j] = a[i][j];
else
{
ans[j] = a[i][j] + max(ans[j] , ans[j + 1]);
}
}
}
cout << ans[1];
return 0;
}