算法導論：第15章 動态規劃_1鋼條切割

/*
鋼條切割:
動态規劃與分治的相同點：組合子問題求解原問題
                不同點：分治的子問題不重疊，做了重複工作，動态規劃儲存解到表中

動态規劃的特點：
1最優子結構：問題的最優解由相關子問題的最優解組合而成，子問題可以獨立求解

公司出售一段長度為i英寸的鋼條價格為Pi(i=1,2,...)，鋼條長度為整英寸
長度i   1	2	3	4	5	6	7	8	9	10
價格Pi	1	5	8	9	10	17	17	20	24	30
給定長度為n的鋼條，求使得的最大收益Rn

分析:
設Rn表示長度為n的鋼條的最大收益，Pn表示長度為n的鋼條的價格,那麼實際上問題對Rn的求解，可以
修改為從不切割也就是Pn,和切分成兩段的最大收益，切分成兩段共有:n-1種切分方法，即
R1+Rn-1,R2+Rn-2,...,Rn-1+R1
狀态轉移方程:
Rn=max(Pn,R1+Rn-1,R2+Rn-2,...,Rn-1+R1)


輸入的第一行是鋼條的長度n

輸入:
4
輸出:
10
*/

#include <iostream>
#include <string.h>

using namespace std;

const int MAXSIZE = 10000;
const int priceArr[11] = {0 , 1 , 5, 8, 9, 10, 17 , 17 , 20 , 24 , 30};
int rArr[MAXSIZE];


int R(int n)
{
	if(!rArr || !priceArr)
	{
		return -1;
	}
	if(rArr[n] != 0)
	{
		return rArr[n];
	}
	int max = priceArr[n];
	for(int i = 1 ; i <= n - 1; i++)
	{
		int value = R(i) + R(n-i);
		if(value > max)
		{
			max = value;
		}
	}
	rArr[n] = max;
	return max;
}

void process()
{
	int n;
	while(cin >> n)
	{
		memset(rArr , 0 , sizeof(rArr));
		int iResult = R(n);
		cout << iResult << endl;
	}
}

int main(int argc, char* argv[])
{
	process();
	getchar();
	return 0;
}