动态规划
1.递归到动规的一般转换方法
递归函数有n个参数，就定义一个n维的数组，数组的下标是递归函数参数的取值范围，数组元素的值是递归函数的返回值，这样就可以从边界值开始，逐步填充数组，相当于计算递归函数值的逆过程
实例：求数字三角形中某一行某一列的点到底边数字的最大和
#include <bits/stdc++.h>
using namespace std;
int D[1005][1005];//用于存储数字三角形
int n;int *max_sum;//在递推过程中将每次的最后一行的max_sum放在一个数组里，每一层遍历完都会实现一次覆盖
//int max_sum[1005][1005];
// int MaxSum(int i,int j)//数字三角形的递归,实际上写成递推形式运行会更快
// {
// if(max_sum[i][j]!=-1) return max_sum[i][j];
// if(i==n) return D[i][j];
// int x=MaxSum(i+1,j);
// int y=MaxSum(i+1,j+1);
// max_sum[i][j] = max(x, y) + D[i][j];
// return max_sum[i][j];
// }
int main()
{
int i,j;
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
cin >> D[i][j];
// max_sum[i][j]=-1;
}
}
max_sum=D[n];//先让max_sum指向第一行
for(int i=n-1;i>0;i--)//动态规划写法，从最后一行开始，用完后max_sum指向的区域立即更新
{
for(int j=1;j<=i;j++)
{
max_sum[j]=max(max_sum[j],max_sum[j+1])+D[i][j];
}
}
cout<<max_sum[1]<<endl;
return 0;
}
2.能用动态规划解决的问题的特点
1）问题具有最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质。
2）无后效性。当前的若干个状态值一旦确定，则此后过程的演变就只和这若干个状态的值有关，和之前是采取哪种手段或经过哪条路径演变到当前的这若干个状态没有关系。
例题一：求最长上升子序列
/*求最长上升子序列*/
#include <bits/stdc++.h>
using namespace std;
int a[10005];
int Max_len[10005];
int cmp(const void *p1, const void *p2)
{
return (*(int *)p1 - *(int *)p2);
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i+1];
}
Max_len[1]=1;
for(int i=2;i<=n;i++)
{
int max=0;
for(int j=1;j<i;j++)
{
if(Max_len[j]>max&&a[j]<a[i])
max=Max_len[j];
}
Max_len[i]=max+1;//求出以a[i]结尾的序列的最大长度
}
//qsort(Max_len,n+1,sizeof(Max_len[1]),cmp);//对n个数排序（写n+1是因为Max_len[0]没有意义）
//cout<<Max_len[n];//输出最大值
//也可使用STL中的max_element()函数进行输出
cout<<*max_element(Max_len+1,Max_len+n+1);
return 0;
}
例题二：求最大公共子序列
/*求最长公共子序列*/
#include <bits/stdc++.h>
using namespace std;
char arr1[1000];
char arr2[1000];
int max_len[1000][1000];
int main()
{
while(cin>>arr1>>arr2)
{
int length1=strlen(arr1);
int length2=strlen(arr2);
int nTmp;
//边界值：先把max_len[i][0]和max_len[0][i]置为零
for(int i=0;i<length1;i++)
max_len[i][0]=0;
for(int j=0;j<length2;j++)
max_len[0][j]=0;
for(int i=1;i<=length1;i++)
{
for(int j=1;j<=length2;j++)
{
if(arr1[i-1]==arr2[j-1])
max_len[i][j]=max_len[i-1][j-1]+1;
else
max_len[i][j]=max(max_len[i-1][j],max_len[i][j-1]);
}
}
cout<<max_len[length1][length2]<<endl;
}
return 0;
}
例题三：最佳加法表达式
/*最佳加法表达式*/
#include <bits/stdc++.h>
using namespace std;
int V[55][1005];
int pos=1;
int Num(int i,int n)//返回n的第i位至最后一位所组成的数
{
int position=1,nn=n;
while(nn/=10) position++;
return n%(int)pow(10,position-i+1);
}
int Num2(int i,int n)//返回n的前i位组成的数字
{
return n/pow(10,(pos-i));
}
int main()
{
int n,m;
cin>>n>>m;
int num = n;
while (num /= 10) pos++;
for(int i=0;i<=m;i++)
{
for(int j=1;j<=pos;j++)
{
if(i==0)
V[i][j]=Num2(j,n);
else if(i+1>j)
V[i][j]=247483646;
else
{
int min=247683646;
for(int k=0;k<j-i;k++)
{
if((V[i-1][i+k]+Num(i+k+1,Num2(j,n)))<min)
{
min=V[i-1][i+k]+Num(i+k+1,Num2(j,n));
}
}
V[i][j]=min;
}
}
}
cout<<V[m][pos];
return 0;
}
