想不到复杂度低的办法。
要说动态规划的话,有一个搭上边的算法,就是把它看作最大团或者最大独立集问题,用状态压缩的动态规划来求解。
方法是:1、建立这样一张图:枚举所有C(m,n)种选课方法,每种选法作为图中的一个节点,两种选法如果冲突,所对应的两个节点间就连一条边,否则不连边。
2、然后用状态压缩的动态规划求这个图的最大独立集。
这个第二步你搜一下“动态规划求最大独立集"或者“动态规划求最大最大团"应该就能找到解法。
但这个复杂度极高,达到了2^C(m,n),可能不是老师想要的解。如果你知道了更好的解法请告诉我,我也很好奇要怎么做