力扣 877. 石子游戏

解题思路使用动态规划阶其中dp[i][j] 表示子数组 p[i][j]下alice与bob拿到的石子之差最小值。公式f[i][j] max(p[i] - dp[i 1][j], p[j] - dp[i][j- 1];f[i][i] p[i];代码实现class Solution { public: int n; int dp[510][510]; bool stoneGame(vectorint p) { n p.size(); for (int i 0; i n; i) dp[i][i] p[i]; for (int i n - 2; i 0; i--) { for (int j i 1; j n; j) { dp[i][j] max(p[i] - dp[i 1][j], p[j] - dp[i][j - 1]); } } return dp[0][n - 1] 0; } };