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为竖向的格子数）从棋盘左上角出发沿着边缘线从左上角走到右下角，总共有多少种走法，要求不能走回头路，即：只能往右和往下走，不能往左和往上走。