สมมติว่าเรากำลังเล่นเกมเดา กฎของเกมมีดังนี้ -
- ผู้เล่น1 เลือกตัวเลขตั้งแต่ 1 ถึง n ผู้เล่น2 ต้องเดาว่าผู้เล่นเลือกหมายเลขใด1.
- ทุกครั้งที่ผู้เล่น 2 เดาผิด ผู้เล่น 1 จะบอกว่าหมายเลขที่เลือกสูงหรือต่ำ
อย่างไรก็ตาม เมื่อผู้เล่นเดาหมายเลข x โดยเฉพาะ และผู้เล่นคนอื่นเดาผิด ผู้เล่นอีกคนต้องจ่าย $x เกมจะจบลงเมื่อผู้เล่น 2 ได้คำตอบที่ถูกต้อง
ตัวอย่างเช่น ถ้า n =10 และผู้เล่น 1 ได้ 8
- รอบแรก ผู้เล่น 2 บอกเลข 5 ผิด เลขจริงสูงกว่า แล้วเขาจะให้ $5
- รอบที่สอง ผู้เล่น 2 บอกเลขเป็น 7 ผิด เลขจริงสูงกว่า แล้วเขาจะให้ $7
- รอบที่สาม ผู้เล่น 2 บอกเลขเป็น 9 ผิด เลขจริงต่ำกว่า แล้วเขาจะให้ $9
ตอนนี้เกมจบลง ดังนั้นเงินทั้งหมดที่ได้รับคือ $5 + $7 + $9 =$21
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- สร้างวิธีหนึ่งที่เรียกว่าต้นทุน ซึ่งกำลังต่ำ สูง อีกตารางหนึ่ง dp
- ถ้าต่ำ>=สูง ให้คืนค่า 0
- ถ้า dp[ต่ำ สูง] ไม่ใช่ -1 ให้คืนค่า dp[ต่ำ สูง]
- ตอบ :=inf
- สำหรับผมอยู่ในช่วงต่ำไปสูง
- ans :=ขั้นต่ำของ ans และ (i + สูงสุดของต้นทุน (ต่ำ, i – 1, dp) และต้นทุน (i + 1, สูง, dp))
- dp[low, high] :=ans และ return ans
- วิธีการจริงจะเป็นเช่น −
- สร้างอาร์เรย์ 2d หนึ่งรายการที่เรียกว่า dp ของขนาด (n + 1) x (n + 1) แล้วเติมด้วย -1
- ผลตอบแทน (1, n, dp)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int cost(int low, int high, vector < vector <int> >& dp){
if(low >= high)return 0;
if(dp[low][high] != -1)return dp[low][high];
int ans = INT_MAX;
for(int i = low; i <= high; i++){
ans = min(ans, i + max(cost(low, i - 1, dp), cost(i + 1, high, dp)));
}
return dp[low][high] = ans;
}
int getMoneyAmount(int n) {
vector < vector <int> > dp(n + 1, vector <int> (n + 1, -1));
return cost(1, n, dp);
}
};
int main() {
Solution ob1;
cout << ob1.getMoneyAmount(8) << endl;
return 0;
} อินพุต
8
ผลลัพธ์
12
