算法设计与分析学习笔记

填空：

1、【算法】由有限条指令构成，每条指令规定了计算机所要执行的有限次运算或者操作。

2、一个最优决策序列的任何子序列本身一定是相对于子序列的【初始和结束状态】的最优的决策序列.

3、贪心算法的证明通常需要证明该算法能够找到问题的最优解。除了数学归纳法之外，还有【交换论证法/反证法】证明方法。

4、分治算法通常都是递归算法，这种算法的时间复杂度分析通常需要求解【递推方程】。

5、可行流f是最大流的充分必要条件是不存在关于f的s-t【增广链】。

选择：

无。

大题：

1、归并排序

没啥好说的。

2、田忌赛马

二千多年前的战国时期，齐威王与大将田忌赛马。双方约定每人各出300匹马，并且在
上、中、下三个等级中各选一匹进行比赛，由于齐威王每个等级的马都比田忌的马略强，
比赛的结果可想而知。现在双方各n匹马，依次派出一匹马进行比赛，每一轮获胜的一方
将从输的一方得到200银币，平局则不用出钱，田忌已知所有马的速度值并可以安排出场
顺序，问他如何安排比赛获得的银币最多。

参考答案：

3、解空间树绘制、最优解，最优值，含义解释

4、动态规划问题-小民走迷宫

int minPathForDP(){
    // 边界情况
    dp[0][0] = a[0][0];
    for(int j = 1; j <n; j++) {
        dp[0][j] = dp[0][j-1] + a[0][j];
    }
    for(int i = 1; i <m; i++) {
        dp[i][0] = dp[i-1][0] + a[i][0];
    }
    
    for(int i = 1; i <m; i++) {
        for(int j = 1; j <n; j++) {
            dp[i][j] = a[i][j] + min(dp[i-1][j], dp[i][j-1]);
        }
    }
    return dp[3][3];
}