486. Predict the Winner
这是很难的一道题目,起初想过很多种与动态规划无关的解决方法,比如每次只考虑前面两个数和后面两个数,以此来进行决策,后来发现这种方法在四个数相差很大的一些情况会出现错误,最后只能又回到动态规划的方法来。当然,我个人并想不出动态规划的具体方法,只好参考了网上的一些做法。
我们将从第i个数到第j个数之间player1能得到的最多的分数记为sco[ i ][ j ],则sco[ i ][ j ]等于sum[ i ][ j - 1 ] - sco[ i ][ j - 1 ] + nums[ j ] 和sum[ i + 1 ][ j ] - sco[ i + 1 ][ j ] + nums[ i ] 中较大的一个(因为我们的选择是为了得到更大的分数)。sum[ i ][ j - 1 ] - sco[ i ][ j - 1 ] + nums[ j ]指的是player1取nums[ j ],于是在第i个数到第j个数之间得到的分数就是nums[ j ]加上从第i个数到第j - 1个数的总和减去其中player2的分数(也就是player2 拿到的最大分数,因为每个player都令自己拿到的分数最大化)。sum[ i + 1 ][ j ] - sco[ i + 1 ][ j ] + nums[ i ]同理。
但是,由于每次都取一次sum[ i ][ j ]非常麻烦,会增加算法的时间复杂度,而问题又不要求我们计算各自能得到的最大分数,只要求得到是否能获胜,那我们就不求能拿到的最大分数,我们将player1 和player2 的分数相减,得到一个差,每次算到各自的分数时,都更新一次分数差,最后看差是否大于等于0,也就知道能否取胜。化简后差win[ i ][ j ]的表达式为win[ i ][ j ] = max(nums[ j ] - win[ i ][ j - 1 ], nums[ i ] - win[ i
+ 1 ][ j ])。
代码如下: