leetcode 困难题 1563. 石子游戏 V-Stone Game V

Problem: 1563. 石子游戏 V-Stone Game V动态规划的呢先求出前缀和prefixdp[i][j]表示区间[i-1, j-1]内石子的最大得分初始化 dp[i][i1] min(stoneValue[i-1], stoneValue[i]);也就是两个石子去掉最大值得分就是次小值递推公式是对dp[i][j]枚举i到j-1做分割点像dp[1][3][2, 3, 5]分割点分别是[[2], [3, 5]], [[2,3],[5]]也就是分割点是【12】对应石子【23】对每个分割点k分割成两部分利用前缀和求出左侧部分的和a, 右侧部分的和c若ac丢弃左侧保存右侧 dp[k1][j]c若ac丢弃右侧保存左侧 dp[i][k] a若ac取最大值, max(dp[i][k], dp[k1][j]) a最后返回dp[1][n]Codeclass Solution { public: int stoneGameV(vectorint stoneValue) { int n stoneValue.size(), mx, a, c, tmp, tmp2; vectorint prefix{0}; vectorvectorint dp(n 1, vectorint(n 1, 0)); for(int i 1; i n; i) { dp[i][i1] min(stoneValue[i-1], stoneValue[i]); prefix.push_back( prefix.back() stoneValue[i-1] ); } prefix.push_back( prefix.back() stoneValue.back() ); for(int i n - 2; i 1; i--) { tmp prefix[i-1]; for(int j i 2; j n; j) { mx 0; tmp2 prefix[j]; for(int k i; k j; k) { a prefix[k] - tmp; c tmp2 - prefix[k]; if(a c) { mx max(mx, dp[k1][j] c); } else if(a c) { mx max(mx, dp[i][k] a); } else { mx max(mx, max(dp[i][k], dp[k1][j]) a); } } dp[i][j] mx; } } return dp[1][n]; } };