#include <iostream>
#include <stdio.h>
#define W 24
using namespace std;
int C[W+1]={0};
int S[W+1]={0};
int d[]={1,5,7,12,20,50};
int N=6;
int main()
{
int i,j;
C[0]=0;
S[0]=0;
for(i=1;i<=W;i++)
{
C[i]=99;
}
for(i=0;i<N;i++)
{
for(j=1;j<=W;j++)
{
if(C[j]>(C[j-d[i]]+1) && d[i]<=j)
{
C[j]=C[j-d[i]]+1;
S[j]=i;
}
}
for(j=1;j<=W;j++)
{
printf("%3d",C[j]);
}
printf("\n");
for(j=1;j<=W;j++)
{
printf("%3d",S[j]);
}
printf("\n\n");
}
return 0;
}
==============================================
#include <stdio.h>
#include <string.h>
#include <iostream>
#define M 8
#define N 8
using namespace std;
char S1[M+1];
char S2[N+1];
char C[M+1][N+1]={0};
int main()
{
int i,j;
strcpy(&S1[1],"A$CMA*MN");
strcpy(&S2[1],"AXMC4ANB");
for(i=1;i<=M;i++)
{
for(j=1;j<=N;j++)
{
if(S1[i]==S2[j]) C[i][j]=C[i-1][j-1]+1;
else if(C[i-1][j]>C[i][j-1])
{
C[i][j]=C[i-1][j];
}else
{
C[i][j]=C[i][j-1];
}
}
}
for(i=1;i<=M;i++)
{
for(j=1;j<=N;j++)
{
printf("%3d",C[i][j]);
}
printf("\n");
}
return 0;
}
