DP，直接递推比记忆化搜索简单。
定义状态\(dp[i][j]\)为前i行最后一个选择第i行第j个数所得到最大值。
易得状态转移方程
\(dp[i][j]=max(dp[i-1][k]+a[i][j])\)
这个题比较困难的就是在\(j\)和\(k\)的枚举上。\(j\)要满足选\(j\)的时候一定要比\(i\)大，比\((m-(n-i))\)小，只有这样才能使前i朵花都可选，后i朵花都可选。而k因为在上一行，所以只需要比j小就好。
#include <bits/stdc++.h>
using namespace std;
const int _INF = -2054847099;
int n, m, maxn;
int a[1001][1001];
//dp[i][j]是必须选择第i，j个数的最大值。
int dp[1001][1001], pre[1001][1001];
int main()
{
memset(dp, -123, sizeof(dp));
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%d", &a[i][j]);
for (int i = 1; i <= m; i++)
dp[1][i] = a[1][i];
for (int i = 2; i <= n; i++)
for (int j = i; j <= m - (n - i); j++)
{
for (int k = 1; k < j; k++)
{
if (dp[i][j] < dp[i - 1][k] + a[i][j])
{
dp[i][j] = dp[i - 1][k] + a[i][j];
pre[i][j] = k;
}
}
}
int maxn = 0, maxk;
for (int i = 1; i <= m; i++)
if (maxn < dp[n][i])
{
maxn = dp[n][i];
maxk = i;
}
printf("%d\n", maxn);
stack <int> s;
s.push(maxk);
while (n)
{
maxk = pre[n--][maxk];
s.push(maxk);
}
s.pop();
while (s.size())
{
printf("%d ", s.top());
s.pop();
}
return 0;
}