12/6
租用游艇问题
r(i,j)表示游艇出租站i到j之间的租金
m(i,j)表示从出租站i出发，到达第i+j站需要的最少租金
例如m(1,3)就表示从第1站出发，到达第4站所需的最少租金
而m(1,3)可以有多种租用方案，例如可以1-2，2-4 或者1-2,2-3,3-4，或者1-3,3-4
由此可以得出递归式：
m(i,j) = min{ m(i,s)+m(i+s,j-s) , r(i,i+j) } 2 ≤j ≤n-i ,1 ≤s < j
且m(i,1) = r(i,i+1);m(n,1) = 0;
其中有两个关键的数组，一个是r(i,j)就是问题给出的第i站到第j站的租金
m(i,j)是从i站到i+j站最少的租金
这里可以得到一个递归的式子
m(i,j)=min{m(i,s)+m(i+s,j-s) , r(i,j) }
有中间站点过渡的结果跟两站点之间的两个结果进行对比，取小的那个
由于我们可能在中间站点停留不止一次，所以我们采取的是一个递归的式子。
核心代码
void solve(int n){
int m[n+1][n+1];
//初始化m数组
for(int i = 1; i <= n; i++){
//m(i,1) = r(i,i+1);m(n,1) = 0;
if(i == n) m[i][1] = 0;
else m[i][1] = r[i][i+1];
for(int j = 2; j <= n; j++){
m[i][j] = MAX_INT;
m[n][j] = 0;
}
}
//自顶向下递归计算
for(int i = n-1; i >= 1; i--){//从第n-1站开始计算 ，如果从i=n开始，则m[n][j] = 0,从终点站开始是没有意义的
for(int j = 2; j <= n-i ; j++){//j从2开始，因为如果j等于1，就是m[i][1]=r[i][i+1],已经是最小值了
for(int s = 1; s < j; s++){//s表示在i~i+j中间的i+s站归还游艇，并从i+s站开始下一阶段的旅行
int minf;
minf = Min(m[i][s]+m[i+s][j-s],r[i][i+j]);
if(minf < m[i][j])
m[i][j] = minf;
}
}
}
printf("%d",m[1][n-1]);
}
题目给出的输入的测试样例
3
5 15
7
解题要点
1.m(i,j)=min{m(i,s)+m(i+s,j-s) , r(i,j) }
2.初始化m数组时如果不是n到n,先一律初始化成r(i,j),r(n,n)==0
编辑距离问题
【样例输入】
fxpimu
xwrs
删除其实是d[i-1][j]+1（i-1转换为j-1的编辑距离再加1，这个1是删除的操作），同理插入可表示为d[i][j-1]+1，那修改如何表示呢？我们想象在进行字符操作后（计算d[][]的过程中），i-1和j-1已经完全相等，那么各给它们两个后再添加一个字符，那么修改就取决于添加的两个字符相不相等，如果相等d[i][j] = d[i-1][j-1]，如果不相等d[i][j] = d[i-1][j-1]+1（就修改一次）。
个人理解：
1.删除/插入分别是d[i-1][j]+1]/d[i][j-1]+1
emmm,这边删除时A的长度为i-1时向长度j的B转化，
#include <stdio.h>
int d[100][100] ;
int min(int a, int b)
{
if(a > b){
return b ;
}
else
return a ;
}
int lenth(char A[])
{
int len = 0, i ;
for(i=0; A[i]!='\0'; i++){
len++ ;
}
return len ;
}
void calculate(char A[], char B[])
{
int i, j ;
for(i=0; i<=lenth(A); i++) d[i][0] = i ;
for(j=0; j<=lenth(B); j++) d[0][j] = j ;
for(i=1; i<=lenth(A); i++){
for(j=1; j<=lenth(B); j++){
if(A[i] == B[j]){
d[i][j] = d[i-1][j-1] ;
}
else {
d[i][j] = d[i-1][j-1] + 1 ;
}
printf("d[i-1][j]+1 = %d, d[i][j-1]+1 = %d, d[i][j] = %d\n", d[i-1][j]+1, d[i][j-1]+1, d[i][j]) ;
d[i][j] = min( d[i][j], min( d[i-1][j]+1, d[i][j-1]+1 ) ) ;
printf("%d\n", d[i][j]) ;
}
}
汽车加油行驶问题
9 3 2 3 6
0 0 0 0 1 0 0 0 0
0 0 0 1 0 1 1 0 0
1 0 1 0 0 0 0 1 0
0 0 0 0 0 1 0 0 1
1 0 0 1 0 0 1 0 0
0 1 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0 1
1 0 0 1 0 0 0 1 0
0 1 0 0 0 0 0 0 0
f(x,y,0)表示从（1,1）到（x,y）所需最少费用。
f(x,y,1)表示从汽车行驶到（x,y）还能行驶的网格边数。
最终即求f[N][N][0]
递归表达式及主要思路：
1.比如现在到了（x,y）,上个位置有4种可能abcd（不过考虑越界的情况，有时候小于4），这四个位置都对应一个费用。
2.比如先选择上个位置是a，现在再去考虑当前位置（到油站否，有没有有油），并加上相应的价格。
3.这是我们会得到一个（x,y）处的费用=a位置费用+当前位置的费用。
4.我们遍历4个位置，寻找到(x,y)处的最小费用即可。
f(1,1,0)=0 f(1,1,1)=k 初始
f(x,y,0)=min{f(x+s[i][0],y+s[i][1],0)+s[i][2]} (1<=i<=4) 从上个位置到达（x,y）,"上个位置"有四种情况。
f(x,y,1)=f(x+s[j][0],y+s[j][1],1)-1
f(x,y,0)=f(x,y,0)+A f(x,y,1)=k (x,y)是油库
f(x,y,0)=f(x,y,0)+C+A f(x,y,1)=k (x,y)是不是油库，但是此时没有油了f(x,y,1)=0
其中s数组表示的四个方向的走向
s={{1，0，0},{0，1，0},{1，0，B},{0，1，B}}//第三个参数时价格B,
解题思路
1.当前位置处于（x,y）
2.向上回溯，考虑来的位置对应的四种费用，然后递归
#include <iostream>
#define INF 100000;
using namespace std;
int main()
{
int N,K,A,B,C;
cin>>N>>K>>A>>B>>C;
int a[N+1][N+1];//N*N的那个网格
for(int i=1;i<=N;++i)
for(int j=1;j<=N;++j)
cin>>a[i][j];
int f[N+1][N+1][3];
for(int i=1;i<=N;++i)
for(int j=1;j<=N;++j)
{f[i][j][0]=INF;f[i][j][1]=K;}//初始化
int s[4][3]={{-1,0,0},{0,-1,0},{1,0,B},{0,1,B}};//4个方向，第三个参数是价格B
f[1][1][0]=0;f[1][1][1]=K;//起点值初始化
for(int x=1;x<=N;++x)
for(int y=1;y<=N;++y)
{
if(x==1&&y==1) continue;
int minmoney=INF;int minstep;//minmoney存储（x,y）上个位置的最小money
int tmpmoney,tmpstep;
for(int i=0;i<=3;++i)//遍历上一个位置的所有可能情况
{ if(x+s[i][0]<1||x+s[i][0]>N||y+s[i][1]<1||y+s[i][1]>N) continue;//超边界
tmpmoney=f[x+s[i][0]][y+s[i][1]][0]+s[i][2];
tmpstep=f[x+s[i][0]][y+s[i][1]][1]-1;
if(a[x][y]==1) {tmpmoney+=A;tmpstep=K;} //遇油站
if(a[x][y]==0&&tmpstep==0&&(x!=N||y!=N)) {tmpmoney+=A+C;tmpstep=K;}//没油了
if(minmoney>tmpmoney)//更新最小值 (最后储存上个位置中费用最少的)
{
minmoney=tmpmoney;
minstep=tmpstep;
}
}
if(f[x][y][0]>minmoney)//更新f
{
f[x][y][0]=minmoney;
f[x][y][1]=minstep;
}
}
cout<<endl;
for(int i=1;i<=N;++i)
{
for(int j=1;j<=N;++j)
cout<<f[i][j][0]<<' ';
cout<<endl;
}
return 0;
}
这里不太知道，
最小m段和问题
int solve(int a[],int n,int m){
int i,j,k,t[n+1][m+1],M[n+1][m+1],sum,getMax;
//初始化
for(i=0;i<=n;i++)//其他
for(j=0;j<=m;j++)
t[i][j]=M[i][j]=MaxInt;
t[0][0]=M[0][0]=0;//0段&&0数据
for(j=1;j<=m;j++){//划分成1~m段
for(i=j;i<=n;i++){//用j~n个数据
sum=0;//i个数据划分成j段。第j段的和
for(k=i;k>=j;k--){//第j段的左端点
sum+=a[k-1];
getMax=max(t[k-1][j-1],sum);
if(getMax<t[i][j] ){
t[i][j]=getMax;
M[i][j]=k;//记录划分点
}
}
}
}
//输出
i=n;j=m,k=m-1;
int mark[m+1];
while(i>=1&&j>=1){
mark[k]=M[i][j];
i=mark[k]-1;
k--;j--;
}
mark[m]=n+1;
i=1;k=0;
while(i<=n){
cout<<"{";
for(;i<mark[k+1];i++){
cout<<a[i-1]<<' ';
}
cout<<"}";
k++;
}
cout<<"\n";
return t[n][m];
}
解题思路
1.当j=1时，dp[i][1]表示的是长为i的整个序列的和；
当j>1时，dp[i][j] = MIN(for(k=1; k<=i; k++)MAX(dp[k][j-1], dp[i][1] - dp[k][1]));
递归得到的i长度分为j段的最小字段和与后面一整个大子段作比较，一直递归一直爽，一直保留最小的那一个，好吧，这是真的爽
k前，k后谁小要谁，然后往后找，递归
最少硬币
#include <stdio.h>
#include<string.h>
#define MAX 20002
#define INF 9999999
#define min(a,b) (a)>(b)?(b):(a)
int T[11], Coins[11], n;//硬币面值数组 T[],可以使用的各种面值的硬币个 数数组 Coins[],n 种不同面值的硬币
int c[MAX];//数组 c[]存放要找的最少硬币个数
int w[11];
int m; //要找的钱数 m
void init()
{
int i;
printf("输入硬币的面值种数：");
scanf_s("%d",&n);
printf("输入硬币面值及其此面值硬币的个数：\n");
for (i = 0; i < n; ++i)
scanf_s("%d %d", &T[i], &Coins[i]);
printf("输入要找的钱数：");
scanf_s("%d", &m);
}
int main()
{
int i, j, k;
init();
for (i = 0; i <= m; ++i)
c[i] = INF; c[0] = 0;
for (i = 0; i < n; ++i)
{
for (j = 1; j <= Coins[i]; ++j)
{
for (k = m; k >= T[i]; --k)
c[k] = min(c[k], c[k - T[i]] + 1);
}
}
if (c[m] != INF)
{
int t,q=c[m],p=m;
printf("最少硬币个数为：%d\n", c[m]);
for (i = m; i>=0; i--)
{
if (c[i] == c[p]-1)
{
t = p-i;//记录所选的硬币
for (j = 0; j < n; j++)
{
if (t == T[j])//找到所选的硬币
w[j]++;//进行硬币计数
}
p = i;
}
}
for (i = 0; i < n; i++)
{
if(w[i]!=0)//如果该硬币没有被选，则为零，不用输出
printf("面值为%d的硬币有%d个\n",T[i],w[i]);
}
}
else
printf("\n -1\n");
return 0;
}
a[k]=min(a[k],a[k-Coins[i]]+1);
12/7
n皇后问题
解决思路
if(pos[i] == pos[k] || fabs(i-k) == fabs(pos[i] - pos[k]))
首先肯定不在同一行，那么我们试图确定这个几个皇后不在同一列，同一斜对角线
三要素：
解空间
约束条件
状态树
虽然n皇后找的代码实在没看懂，试图搞懂了八皇后的思路，两个没什么差距1.根据a[i]==a[n]||abs(a[i]-a[n])==abs(i-n)形成约束条件，以i,n为横坐标，i<n这个时候来判断不在同一行，并且不在同一对角线，并且通过返回的整数值的不同，判断有没有通过约束条件
2.一旦i没有通过约束条件，我们通过n+1,在快乐的棋盘上继续往后找
3.直到找到最后一行n==max-1停止寻找，这时候我们可以输出皇后可以存在的位置https://www.cnblogs.com/Mayfly-nymph/p/8506158.html
参考文章