类比背包问题思考状态表示和状态转移方程

1.状态表示：从前i朵花中选 把第i朵花插入第j个花瓶 dp[i][j]为最大美学值
2.状态转移方程 dp[i][j] = max(dp[i][j], dp[i - 1][k] + g[i][j]) 因为第i朵花插入第j个花瓶，根据题目要求，前i-1朵花只能在[1,j-1]个花瓶中选择花瓶插入，因此k取值范围为[0,j-1]，0表示没有花瓶

算法1 (DP)

C++ 代码

#include <iostream>
#include <vector>

using namespace std;

const int N = 110;

int dp[N][N];
int g[N][N];
int pre[N][N];
int f, v;
vector<int> vec;

int main()
{
    cin >> f >> v;

    for(int i = 1; i <= f; i ++)
        for(int j = 1; j <= v; j ++)
            cin >> g[i][j];

    memset(dp, -0x3f, sizeof dp);

    for(int j = 0; j <= v; j ++)
        dp[0][j] = 0;//初始化 没有花时每一个花瓶美学值都为0

    for(int i = 1; i <= f; i ++)
        for(int j = 0; j <= v; j ++)
            for(int k = 0; k < j; k ++)
            {
                if(dp[i][j] < dp[i - 1][k] + g[i][j])
                {
                    dp[i][j] = dp[i - 1][k] + g[i][j];
                    pre[i][j] = k;//保存当前状态由哪一个花瓶转移过来
                }
            }

    //选择f朵花且第f朵花插入第t个花瓶的最大美学值       
    int t = -1e9, y;
    for(int j = 1; j <= v; j ++)
        if(dp[f][j] > t)
        {
            t = dp[f][j];
            y = j;
        }

    cout  << t << endl;

    vec.push_back(y);

    for(int i = f; i >= 2; i --)
    {
        vec.push_back(pre[i][y]);
        y = pre[i][y];
    }

    for(int i = vec.size() - 1; i >= 0; i --)
        cout << vec[i] << ' ';
}