本题属于计数型动态规划问题,我们可以定义出状态dp[i][j]表示1~i的数字拆分成两个子数组求和的差的绝对值为j的方案数。 方程为 dp[i][j] = dp[i-1][j+i] + dp[i-1][abs(j-i)] 答案需要特判m == 0时的情况,例如n=3, m=0时,只有一组A1={1, 2}, A2={3},但使用dp会将正反计算两次,因此需要对结果除以2; 其他情况下,不会出现正反计算两次的情况,因此直接输出即可。
注册一个 核OJ_核桃编程 通用账户,您就可以在我们提供的所有在线评测服务上提交代码、参与讨论。
使用您的 核OJ_核桃编程 通用账户