23/2/22学习记录（最小公倍数，动态规划）
1. printf( )输出时保留小数则需要printf("%0.xf",n)，保留x位小数
2. 求最大公因数和最小公倍数，最小公倍数即是两数之积除以最大公因数。
int func1(int a,int b)
{
int temp;
while(a*b!=0)
{
temp=a%b;
a=b;
b=temp;
}
return a;
}
3. 动态规划
- 判断依据：1.计数（如多少种方式走到右下角，多少种方法选出k个数使和为sum）
2.最值（如左上到右下路径最大，最长上升子序列）
3.存在性（如取石子，能不能选出k个数使和为sum）
- 组成部分：（举例理解： 由三种硬币面值分别为2，5，7组合成27，要求硬币数最少）
- 1. 确定状态：创建一个数组f[ ]或者dp[ ][ ]等，每个元素代表什么，相当于定义未知数。确定状态需要两个意识：
- -最后一步
- （最优策略：K枚硬币a1、...、ak，一定有最后的硬币ak，除掉最后一枚，前面和为27-ak），不关心K-1枚硬币怎么拼出27-ak，甚至不知道K，ak，但确定前面的硬币拼出27-ak，但是因为是最优策略，所以拼出27-ak的硬币数一定要少
- 子问题。
- 最少要用多少枚硬币拼出27-ak，于是将问题转化成一个子问题并且规模更小，简化定义设状态f（X)=最少用多少枚硬币拼出X。最后的ak只能是2、5、7，所以f[ 27 ]=f[ 27-2|5|7 ]+1
- 所以f[ X ]=min{f[ X-2 ]+1，f[ X-5 ]+1，f[ X-7 ]+1}
- 2. 转移方程：
- 设f[X]=最少用多少枚硬币拼出X，对任意X，有f[ X ]=min{f[ X-2 ]+1，f[ X-5 ]+1，f[ X-7 ]+1}
- 3. 初始条件和边界情况：
- f[ X ]=min{f[ X-2 ]+1，f[ X-5 ]+1，f[ X-7 ]+1}，X-2|X-5|X-7小于0怎么办？什么时候停下来？
- 若不能拼出f（Y）则定义f（Y）=正无穷
- 初始条件f[ 0 ]=0
- 4. 计算顺序：
- 从小到大或者从上到下从左到右（之前所得结果保存下来）
- 简单题：机器人走方格的方案数，请计算n*m的棋盘格子（n为横向的格子数，m为竖向的格子数）从棋盘左上角出发沿着边缘线从左上角走到右下角，总共有多少种走法，要求不能走回头路，即：只能往右和往下走，不能往左和往上走。
