leetcode 486. Predict the Winner
前に書く
二ブラシの過程の中の経典の動態計画のテーマは、動態計画の過程をより深く、細かく理解するのに役立ちます.
タイトルの説明
Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins.
Given an array of scores, predict whether player 1 is the winner. You can assume each player plays to maximize his score.
Example 1: Input: [1, 5, 2] Output: False Explanation: Initially, player 1 can choose between 1 and 2. If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2). So, final score of player 1 is 1 + 2 = 3, and player 2 is 5. Hence, player 1 will never be the winner and you need to return False. Example 2: Input: [1, 5, 233, 7] Output: True Explanation: Player 1 first chooses 1. Then player 2 have to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233. Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.
構想分析
一つの問題を動的計画で解くことができるかどうかを判断する鍵は,問題自体がサブ問題の組合せに変換できるかどうかである.サブ問題間は,状態遷移方程式によって相関を保つ.後者のサブ問題の解は,前のサブ問題が状態遷移方程式によって解いたものである.これにより,動的計画問題の解は問題規模と関係なく,サブ問題間の関連を構成する状態遷移方程式を見つけることが肝心であるという基本的な結論が得られる.いくつかの問題の状態遷移方程式はあまり明らかではなく、解きにくい(leetcode 241状態遷移は演算子によって体現される).また,いくつかの問題はトップダウン方式で解くことができ,この解法は通常再帰を解法として用いる.上から下への過程は,通常分子問題を解く過程であるため,通常は下から上への方法で解くこともでき,本題はこのクラスに属する.
私たちはまず上から下への問題解を書いてから、下から上への過程を考えます.本題では、タイトルの要求は勝者を予測することであり、2人はそれぞれ配列の両端から選択し、彼らはいずれも最適な方法で選択する.ここには、勝者が最後に得た点数が必ず他方より多いことを知っているテクニックがある.そのため、ここのダイナミックプランニングアルゴリズムは両者の差を考慮している.つまり、一方が取った点数から他方が取った点数を引いて、最後に0より大きくなれば勝つということです.このような考えが再現されたアルゴリズムは以下の通りである.
非再帰的な書き方は次に更新されます.
二ブラシの過程の中の経典の動態計画のテーマは、動態計画の過程をより深く、細かく理解するのに役立ちます.
タイトルの説明
Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins.
Given an array of scores, predict whether player 1 is the winner. You can assume each player plays to maximize his score.
Example 1: Input: [1, 5, 2] Output: False Explanation: Initially, player 1 can choose between 1 and 2. If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2). So, final score of player 1 is 1 + 2 = 3, and player 2 is 5. Hence, player 1 will never be the winner and you need to return False. Example 2: Input: [1, 5, 233, 7] Output: True Explanation: Player 1 first chooses 1. Then player 2 have to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233. Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.
構想分析
一つの問題を動的計画で解くことができるかどうかを判断する鍵は,問題自体がサブ問題の組合せに変換できるかどうかである.サブ問題間は,状態遷移方程式によって相関を保つ.後者のサブ問題の解は,前のサブ問題が状態遷移方程式によって解いたものである.これにより,動的計画問題の解は問題規模と関係なく,サブ問題間の関連を構成する状態遷移方程式を見つけることが肝心であるという基本的な結論が得られる.いくつかの問題の状態遷移方程式はあまり明らかではなく、解きにくい(leetcode 241状態遷移は演算子によって体現される).また,いくつかの問題はトップダウン方式で解くことができ,この解法は通常再帰を解法として用いる.上から下への過程は,通常分子問題を解く過程であるため,通常は下から上への方法で解くこともでき,本題はこのクラスに属する.
私たちはまず上から下への問題解を書いてから、下から上への過程を考えます.本題では、タイトルの要求は勝者を予測することであり、2人はそれぞれ配列の両端から選択し、彼らはいずれも最適な方法で選択する.ここには、勝者が最後に得た点数が必ず他方より多いことを知っているテクニックがある.そのため、ここのダイナミックプランニングアルゴリズムは両者の差を考慮している.つまり、一方が取った点数から他方が取った点数を引いて、最後に0より大きくなれば勝つということです.このような考えが再現されたアルゴリズムは以下の通りである.
class Solution {
bool PredictTheWinner(vector<int> nums) {
vector<vector<int>> dp(nums.size(),vector<int>(nums.size(),0);
return helper(nums, 0, nums.length-1, dp)>=0;
}
int helper(vector<int>&nums, int s, int e, vector<vector<int>>& dp){
if(dp[s][e]==0)
dp[s][e] = s==e ? nums[e] : max(nums[e]-helper(nums,s,e-1,dp),nums[s]-helper(nums,s+1,e,dp));
return dp[s][e];
}
}非再帰的な書き方は次に更新されます.