一个n×n矩阵，每次随机选出一个数，然后去掉该元素所在的行和列，最终选出n个数，求这n个数的乘积最大值（矩阵中的元素有正有负）。不用写代码，讲思路即可。
考察说明
考察动态规划与状态压缩在组合优化问题上的应用及正负号处理
回答思路
- 识别出这是二分图匹配选数的模型，等价于选取每行每列各一个元素
- 指出暴力枚举全排列是n!不可行，需要DP优化
- 说明用bitmask状态表示已选列，dp[mask]表示处理完前若干行且已选列集合为mask时的最大乘积
- 强调正负号处理：由于元素有正负，需要同时维护最大值和最小值，因为负负得正可能翻转极值
- 说明转移时从当前行选一未用列，更新dp_max和dp_min，最终答案为dp[(1<<n)-1]
本题已收录答题指导
本题附完整参考答案与评分标准
登录后可查看结构化答题指导；也可以直接开一场模拟面试，AI 面试官用本题实时追问并给出评分。