jain12

optimal strategy for a game by DP

Jun 1st, 2020
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.77 KB | None | 0 0
  1. #include<iostream>
  2. #include<math.h>
  3. using namespace std;
  4.  
  5.   int OptimalStrategyOfGame(int arr[],int n){
  6.     int op_val[n][n];
  7.     for(int gap=0;gap<n;gap++){
  8.       for(int i=0,j=gap;j<n;i++,j++){
  9.         int x=(i+2<=j)?op_val[i+2][j]:0;
  10.         int y=(i+1<=j-1)?op_val[i+1][j-1]:0;
  11.         int z=(i<=j-2)?op_val[i][j-2]:0;
  12.         op_val[i][j]=max((arr[i]+min(x,y)),(arr[j]+min(y,z)));
  13.         }
  14.       }
  15.       return op_val[0][n-1];
  16.     }
  17.  
  18. int main(){
  19.   int arr1[] = { 8, 15, 3, 7 };
  20.     int n = 4;
  21.    cout<<OptimalStrategyOfGame(arr1, n)<<endl;
  22.  
  23.     int arr2[] = { 2, 2, 2, 2 };
  24.     n = 4;
  25.    cout<<OptimalStrategyOfGame(arr2, n)<<endl;
  26.  
  27.     int arr3[] = { 20, 30, 2, 2, 2, 10 };
  28.     n = 6;
  29.     cout<<OptimalStrategyOfGame(arr3, n)<<endl;
  30.     return 0;
  31.   }
Add Comment
Please, Sign In to add comment