一.POJ 1157 小花店问题

dp[i][j]表示前i朵花放入前j个瓶子得到的最大价值。

因为要求j>i，所以有两种放法：

（1）当i=j的时候dp[i][j]=v[1][1]+v[2][2]+v[i][j]+……

（2）当j>i的时候dp[i][j]=max(dp[i][j-1],dp[i-1][j-1]+v[i][j]);

#pragma comment(linker, "/STACK:1024000000,1024000000")
//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<bitset>
#define mem(a,b) memset(a,b,sizeof(a))
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define llson j<<1,l,mid
#define rrson j<<1|1,mid+1,r
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define INF 0x7fffffff
#define maxn 105
int dp[maxn][maxn],v[maxn][maxn];
int main()
{
    int n,m,i,j;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        scanf("%d",&v[i][j]);
    for(i=1;i<=n;i++)
        dp[i][i]=dp[i-1][i-1]+v[i][i];
    for(i=1;i<=n;i++)
        for(j=i+1;j<=m;j++)
            dp[i][j]=max(dp[i][j-1],dp[i-1][j-1]+v[i][j]);
    cout<<dp[n][m]<<endl;
    return 0;
}

动态规划专题