Educoder程序设计2算法练习
educoder 的程序设计 2 练习题，题型挺多样的，像图的遍历、动态规划、搜索都有，适合用来练练算法功底。
柱子染色的那题挺有意思，每根柱子颜色费用不同，还要相邻不能同色，其实就是经典的最小路径覆盖问题变种，直接套动态规划模板。输入是n*k的矩阵，代表每根柱子涂每种颜色的代价，比如cost[1][2]就表示第 2 根柱子用第 3 种颜色的费用。写起来不算难，但要注意状态转移的时候避开上一根柱子的颜色。
还有一道划分棋盘的题，嗯，这道就比较硬核了。把一个 8*8 的矩形划分成 n 块，要求每块的得分均方差最小，就是让各块得分尽量平均。这类问题比较典型，得用记忆化搜索配合前缀和优化。做的时候可以先预出前缀和，之后每次分块就能快速算得分。
你要是刚开始刷题，这些题确实有点上强度，不过好处是配套的案例和都挺清晰的，不容易掉坑。建议先写柱子染色那题，逻辑比较直，入门友好。
实在卡住，也可以看看这些相关文章，像最小费用流算法、迷宫寻路和A*寻路算法都挺有参考价值，尤其是迷宫那几道，有多语言实现，照着写能学不少套路。
如果你最近在准备面试或者打算提高算法能力，educoder 这套练习还蛮推荐的，练思维又练实现。记得别急，一题一题慢慢搞清楚逻辑就行。
文件大小：617.87KB
评论区