搜狐笔试第二题

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<algorithm>

int main()
{
    int len = 0;
    scanf("%d", &len);
    std::vector<int> nums(len, 0);
    for (int i = 0; i < len; ++i)
    {
        scanf("%d", &nums[i]);
    }

    std::vector<std::vector<int>> dp(len, std::vector<int>(len, std::numeric_limits<int>::max()));

    for (int i = 0; i < len; ++i)
    {
        dp[i][i] = 0;
    }

    int result = 0;
    for (int i = 0; i < len; ++i)
    {
        result += nums[i];
    }

    for (int i = 1; i < len; ++i)
    {
        for (int start = 0; start + i < len; ++start)
        {
            int end = start + i;
            if (nums[start] == nums[end])
            {
                dp[start][end] = std::min(dp[start][end], i <= 1 ? 0 : dp[start + 1][end - 1]);
            }
            dp[start][end] = std::min(dp[start][end], std::min(dp[start + 1][end] + nums[start], dp[start][end - 1] + nums[end]));
        }
    }

    result += dp[0][len - 1];

    printf("%d\n", result);

    system("pause");
    return 0;
}