int main(void) {
	int result[11];
	int p[11] = { 0,1,5,8,9,10,17,17,20,24,30};
	cout << BottomUp(0, p, result) << endl;
	cout << BottomUp(1,p,result) << endl;
	cout << BottomUp(2, p, result) << endl;
	cout << BottomUp(3, p, result) << endl;
	cout << BottomUp(4, p, result) << endl;
	cout << BottomUp(5, p, result) << endl;
	cout << BottomUp(6, p, result) << endl;
	cout << BottomUp(7, p, result) << endl;
	cout << BottomUp(8, p, result) << endl;
	cout << BottomUp(9, p, result) << endl;
	cout << BottomUp(10, p, result) << endl;
	return 0;
}
//自底向上的动态规划
int BottomUp(int n, int p[], int result[]) {
	for (int i = 1; i < n + 1; i++) {
		int tempMaxPrice = -1;
		for (int j = 1; j <= i; j++) {
			int maxPrice = p[j] + result[i - j];
			if (maxPrice > tempMaxPrice)
			{
				tempMaxPrice = maxPrice;
			}
		}
		result[i] = tempMaxPrice;
	}
	return result[n];
}