免费制作网站的基本流程,热点事件舆情分析,wordpress 适应手机,互联网软件外包文章目录 一、递归二、区间动态规划 LeetCode#xff1a;486. 预测赢家
一、递归
注意到本题数据范围为 1 n 20 1n20 1n20#xff0c;因此可以使用递归枚举选择方式#xff0c;时间复杂度为 2 20 1024 ∗ 1024 1048576 1.05 1 0 6 2^{20… 文章目录 一、递归二、区间动态规划 LeetCode486. 预测赢家
一、递归
注意到本题数据范围为 1 n 20 1n20 1n20因此可以使用递归枚举选择方式时间复杂度为 2 20 1024 ∗ 1024 1048576 1.05 × 1 0 6 2^{20} 1024*102410485761.05 × 10^6 2201024∗102410485761.05×106。
对于每一个先手都有两种选择方式我们对该选择方式进行枚举。
我们定义递归函数 p r e d i c t predict predict表示玩家1在当前选择的情况下是否可以胜利注意到每个玩家的玩法都会使他的分数最大化因此对于玩家2的选择如果存在一个选择使得玩家1输那么该情况下玩家1都不能胜利只要玩家2选择让自己赢的情况那么玩家1就不能赢了。但是对于玩家1的选择存在一个选择能赢就算可以赢。
class Solution {
public:bool predictTheWinner(vectorint nums) {return predict(nums, 0, (int) nums.size() - 1, 0, 0, 0);}
private:bool predict(vectorint nums, int left, int right, int player, int score_1, int score_2){if(left right){if(score_1 score_2) return true;else return false;}if(player 0){//玩家一存在一个赢就算赢了if(predict(nums, left 1, right, player ^ 1, score_1 nums[left], score_2)) return true;if(predict(nums, left, right - 1, player ^ 1, score_1 nums[right], score_2)) return true;}else{//玩家二存在一个玩家二赢则玩家一必输。if(predict(nums, left 1, right, player ^ 1, score_1, score_2 nums[left]) predict(nums, left, right - 1, player ^ 1, score_1, score_2 nums[right])) return true;}return false;}
};二、区间动态规划
注意到这里是从大的数组中选择让数组依次减小我们也可以从数组小的开始转移到大数组因为当小数组确定时大数组也能确定。
我们可以定义 d p 1 [ i ] [ j ] [ p l a y e r ] dp1[i][j][player] dp1[i][j][player]表示在选择数组 [ i , j ] [i,j] [i,j]时 p l a y e r player player先手时玩家1的分数类似的有 d p 2 [ i ] [ j ] [ p l a y e r ] dp2[i][j][player] dp2[i][j][player]。
则有状态转移
//玩家1先手dp1[i][j][0] max(dp1[i 1][j][1] nums[i], dp1[i][j - 1][1] nums[j]);if(dp1[i 1][j][1] nums[i] dp1[i][j - 1][1] nums[j]){dp2[i][j][0] dp2[i 1][j][1];if(dp1[i 1][j][1] nums[i] dp1[i][j - 1][1] nums[j])dp2[i][j][0] min(dp2[i 1][j][1], dp2[i][j - 1][1]);}else{dp2[i][j][0] dp2[i][j - 1][1];}
//玩家2先手dp2[i][j][1] max(dp2[i 1][j][0] nums[i], dp2[i][j - 1][0] nums[j]);if(dp2[i 1][j][0] nums[i] dp2[i][j - 1][0] nums[j]){dp1[i][j][1] dp1[i 1][j][0];if(dp2[i 1][j][0] nums[i] dp2[i][j - 1][0] nums[j])dp1[i][j][1] min(dp1[i 1][j][0], dp1[i][j - 1][0]);}else{dp1[i][j][1] dp1[i][j - 1][0];}时间复杂度 O ( N 2 ) O(N^2) O(N2)
class Solution {
public:bool predictTheWinner(vectorint nums) {vectorvectorarrayint, 2 dp1(nums.size(), vectorarrayint, 2(nums.size(), arrayint, 2{}));vectorvectorarrayint, 2 dp2(nums.size(), vectorarrayint, 2(nums.size(), arrayint, 2{}));for(int i 0; i nums.size(); i){dp1[i][i][0] nums[i];dp2[i][i][1] nums[i];}for(int k 1; k nums.size(); k){for(int i 0; k i nums.size(); i){int j i k;//玩家1先手dp1[i][j][0] max(dp1[i 1][j][1] nums[i], dp1[i][j - 1][1] nums[j]);if(dp1[i 1][j][1] nums[i] dp1[i][j - 1][1] nums[j]){dp2[i][j][0] dp2[i 1][j][1];if(dp1[i 1][j][1] nums[i] dp1[i][j - 1][1] nums[j])dp2[i][j][0] min(dp2[i 1][j][1], dp2[i][j - 1][1]);}else{dp2[i][j][0] dp2[i][j - 1][1];}//玩家2先手dp2[i][j][1] max(dp2[i 1][j][0] nums[i], dp2[i][j - 1][0] nums[j]);if(dp2[i 1][j][0] nums[i] dp2[i][j - 1][0] nums[j]){dp1[i][j][1] dp1[i 1][j][0];if(dp2[i 1][j][0] nums[i] dp2[i][j - 1][0] nums[j])dp1[i][j][1] min(dp1[i 1][j][0], dp1[i][j - 1][0]);}else{dp1[i][j][1] dp1[i][j - 1][0];}}}return dp1[0][(int) nums.size() - 1][0] dp2[0][(int) nums.size() - 1][0];}
};简化代码这个代码过了
简化逻辑玩家1先手那么玩家1效益最大玩家2应该效益要最低。 但这个逻辑感觉存在一定问题因为玩家1先手玩家1想要自己的效益最大这个时候玩家2的效益是跟玩家1的选择有关的因为棋局完全根据玩家1来决定。所以一开始我并没有直接使用min求解后手。
class Solution {
public:bool predictTheWinner(vectorint nums) {vectorvectorarrayint, 2 dp1(nums.size(), vectorarrayint, 2(nums.size(), arrayint, 2{}));vectorvectorarrayint, 2 dp2(nums.size(), vectorarrayint, 2(nums.size(), arrayint, 2{}));for(int i 0; i nums.size(); i){dp1[i][i][0] nums[i];dp2[i][i][1] nums[i];}for(int k 1; k nums.size(); k){for(int i 0; k i nums.size(); i){int j i k;//玩家1先手dp1[i][j][0] max(dp1[i 1][j][1] nums[i], dp1[i][j - 1][1] nums[j]);dp2[i][j][0] min(dp2[i 1][j][1], dp2[i][j - 1][1]);//玩家2先手dp2[i][j][1] max(dp2[i 1][j][0] nums[i], dp2[i][j - 1][0] nums[j]);dp1[i][j][1] min(dp1[i 1][j][0], dp1[i][j - 1][0]);}}return dp1[0][(int) nums.size() - 1][0] dp2[0][(int) nums.size() - 1][0];}
};
