USACO Gold - Modern Art 3

Debugging Help
#1

Hello,

I tried to solve Modern Art 3 here, and here’s my code:

// modernArtAgain.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <vector>
#include <limits.h>

const int MAX_N = 300;

int dp[MAX_N + 1][MAX_N + 1];

std::vector<int> vect;

int rec(int a, int b) { // range dp from a inclusive to b exclusive
	if (dp[a][b] != -1) return dp[a][b]; // if dp[a][b] already defined return it

	if (a == b) return dp[a][b] = 0; // if len of substring is 0 return 0
	if (a == b - 1) return dp[a][b] = 1; // if len of substring is 1 return 1
	
	if (vect[a] != vect[b - 1]) {
		dp[a][b] = 1 + std::min(rec(a, b - 1), rec(a + 1, b)); // if ends are different try removing either one of the ends
	}
	else {
		int first_re;
	int last_re;

	dp[a][b] = 1 + rec(a + 1, b - 1);
	
	for (first_re = a + 1; first_re < b - 1; ++first_re) {
		if (vect[first_re] == vect[a]) dp[a][b] = std::min(dp[a][b], rec(a, first_re + 1) + rec(first_re, b) - 1);
	}
           // section takes care of cases like 1 2 3 2 1 4 5 4 1, where the ones can be painted with a single stroke
	

	return dp[a][b];
}


int main()
{
	int len;
	std::cin >> len;
	for (int i = 0; i < len; ++i) {
		int a;
		std::cin >> a;
		if (vect.size() == 0 || vect[vect.size() - 1] != a) {
			vect.push_back(a);
		}
	}

	for (int i = 0; i < MAX_N + 1; ++i) {
		for (int j = 0; j < MAX_N + 1; ++j) {
			dp[i][j] = -1;
		}
	}

	std::cout << rec(0, vect.size());
	std::cout << "\n";
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu

However, using this I only got 6 test cases (1-4) , (11-12). I looked at the editorial, is there a more straightforward solution that doesn’t use the “segment” idea?

Thanks!

#2

Hello, update, I was able to get AC with the state dp[a][b] = dp[a][k] + dp[k][b] - 1 (minimum) for all k, does anyone know why my previous solution doesn’t work?

#3