/*This is the template of *.cpp files */
#include<iostream>
#include<vector>
using namespace std;
int cut_rod(int *p,int n ){//暴力法求最优切割
if(n == 0)
return 0;
int q = -1;
for(int i = 1;i<=n;++i){
q = q>p[i] + cut_rod(p,n-i)?q:p[i] + cut_rod(p,n-i);
}
return q;
}
int end_cut_rod(int *p,int n){//自底向上动态规划算法求最优切割方法的价值 以及切割方案
int *r = new int[n+1];
int *s = new int[n+1];
for(int m = 0;m<=n;++m){
r[m] = 0;
s[m] = 0;
}
for(int i = 1;i <= n;++i){
for(int j = 0;j < i;++j){
int temp = r[j] + p[i-j];
if(r[i] < temp){
r[i] = temp;
s[i] = i - j;
}
}
}
int k = n;
while(k > 0){
cout<<s[k]<<endl;
k = k - s[k];
}
return r[n];
}
int fei(int n){//斐波那契数列之动态规划算法
int *a = new int[n+1];
if(n >= 1)
a[1] = 1;
if(n >= 2)
a[2] = 1;
if(n > 2){
for(int j = 3;j <= n;++j){
a[j] = a[j-1] +a[j-2];
}
}
int k = a[n];
delete[] a;
return k;
}
void printb(int *a,int n,int x,int y){//打印虚拟二位数组，对指定值加括号
for(int i = 1;i<n;i++){
for(int j = 1;j<n;++j){
if(i == x&&j == y){
cout<<"("<<a[(n-1)*(i-1)+j-1]<<")"<<" ";
}else{
cout<<a[(n-1)*(i-1)+j-1]<<" ";
}
}
cout<<endl;
}
}
void printa(int *a,int n){//普通打印虚拟二维数组函数
for(int i = 1;i<n;i++){
for(int j = 1;j<n;++j){
cout<<a[(n-1)*(i-1)+j-1]<<" ";
}
cout<<endl;
}
}
int *matrix_chain_order(int *p,int n){//矩阵链相乘动态规划加括号算法
int *a = new int[(n-1)*(n-1)];
int *b = new int[(n-1)*(n-1)];
for(int i = 1;i<n;++i){
a[(n-1)*(i-1)+i-1] = 0;
}
for(int i = 1;i<n;++i){
for(int j =1;j<n-i+1;j++){
a[(n-1)*(j-1)+j+i-1] = 100000;
for(int k = j;k< j+i;++k){
int temp = p[j-1]*p[k+1-1]*p[j+i-1+1] + a[(n-1)*(j-1)+k-1] + a[(n-1)*(k+1-1)+j+i-1];
if(temp < a[(n-1)*(j-1)+j+i-1]){
a[(n-1)*(j-1)+j+i-1] = temp;
b[(n-1)*(j-1)+j+i-1] = k;
}
}
}
}
printa(a,n);
cout<<endl<<endl;
printa(b,n);
return b;
}
void print_optimal_parens(int *s,int i,int j,int n){//矩阵链加括号函数
if(i == j){
cout<<"A"<<i;
}else{
cout<<"(";
print_optimal_parens(s,i,s[(n-1)*(i-1)+j-1],n);
print_optimal_parens(s,s[(n-1)*(i-1)+j-1]+1,j,n);
cout<<")";
}
}
int main(){
int p[15] = {0,2,3,6,8,10,11,18,19,25,34,56,57,58,65};
cout<<cut_rod(p,14)<<endl<<endl;//暴力切割实例
int test[] = {30,35,15,5,10,20,25};
matrix_chain_order(test,7);//矩阵链生成子问题图
cout<<endl;
cout<<"实现矩阵链加括号:"<<endl;
print_optimal_parens(matrix_chain_order(test,7),1,6,7);//实现矩阵链加括号
cout<<endl;
cout<<"实现动态规划算法切割:"<<endl;
cout<<end_cut_rod(p,14)<<"斐波那契数列之动态规划算法求第30个数的值"<<endl;//实现动态规划算法切割
cout<<fei(30);//斐波那契数列之动态规划算法求第30个数的值
return 0;
}