DP  Intuitive explannations, complete demo, NEVER confused with DP again
Strategy Descriptions:\n\t\n\ti,j  represent the left and right closed interval of str.\n\tdp[i][j]: the max coins of [i,j] using specific delete order.\n\tk: t
Strategy Descriptions:\n\t\n\ti,j  represent the left and right closed interval of str.\n\tdp[i][j]: the max coins of [i,j] using specific delete order.\n\tk: the idx of the last one we delete \n\t\n\tRecurrence Formula: \tdp[i][j] = dp[i][k-1] + dp[k][k] + dp[k+1][j]\n\t\t\t\t\t\t\t\tif(k=i)\tdp[i][j] = 0 + nums[i-1]/0*nums[k]*nums[j+1]/0 + dp[k+1][j];\n\t\t\t\t\t\t\t\tif(k=j)\tdp[i][j] = dp[i][k-1] + nums[i-1]/0*nums[k]*nums[j+1]/0 + 0;\n\n\ti: from len-1 to 0, \t(direction of i never mind) \n\tj: from i to len-1,\t(direction of j should start from i)\n\tk: from i to j.\t(direction of k never mind)\n\n\twe fill the dp[][] table like:\n       j,\u2192,\u2192,\u2192,len-1\n    0 [x,\u2192,\u2192,\u2192,len-1]\n\t\u2191 [\\,x,\u2192,\u2192,len-1]\n    \u2191 [\\,\\,x,\u2192,len-1]\n    \u2191 [\\,\\,\\,x,len-1]\n    i [\\,\\,\\,\\,x]\t\t\tdirection of k never mind)\n\n     or\n\n\t i      [x,\\,\\,\\,\\]\n\t \u2193 \t    [0,x,\\,\\,\\]\n\t \u2193 \t    [0,\u2190,x,\\,\\]\n\t \u2193 \t    [0,\u2190,\u2190,x,\\]\n     len-1 \t[0,\u2190,\u2190,\u2190,x]\n\t 0,\u2190,\u2190,\u2190,j\t\t        direction of k never mind\n\n\tusing [3,1,5,8] as an example, direction of i from len-1 to 0.\n\ti=3,j=3,k=3: \t\tget dp[3][3],\n\ti=2,j=2,k=2: \t\tget dp[2][2],\n    j=3,k=2/3:\t\t    get dp[2][3] relied on dp[3][3] and dp[2][2]\n\ti=1,j=1,k=1: \t\tget dp[1][1]\n    j=2,k=1/2:\t\t    get dp[1][2] relied on dp[2][2] and dp[1][1]\n    j=3,k=1/2/3:\t    get dp[1][3] relied on dp[2][3] and dp[1][1],dp[3][3] and dp[1][2]\n\t\u2026\n\t\n\tMaximum Order: using [3,1,5,8] as example.    \n\t\tdp[0][3]\t= 1*8*1 + dp[0][2]\tselect 8 as the last one\t/ forth\n\t\t\t\t\t= 1*8*1 + 1*3*8 + dp[1][2]\t\tselect 3 as the last two\t/ third\n\t\t\t\t\t= 1*8*1 + 1*3*8 + 3*5*8 + dp[1][1]\tselect 5 as the last three \t/ secon\n\t\t\t\t\t= 1*8*1 + 1*3*8 + 3*5*8 + 3*1*5\tselect 1 as the last four \t/ first\n\t\n\tRecurrence Formula: \t\tdp[i][j] = dp[i][k-1] + dp[k][k] + dp[k+1][j]\n\t\t\tif(k=i)\tdp[i][j] = 0 + nums[i-1]/0*nums[k]*nums[j+1]/0 + dp[k+1][j];\n\t\t\tif(k=j)\tdp[i][j] = dp[i][k-1] + nums[i-1]/0*nums[k]*nums[j+1]/0 + 0;\n\n\n\nCode:\n\t\t\t\t\t\n```\npublic int maxCoins(int[] nums) {\n\t// Corner Case\n\tif(nums == null || nums.length == 0) return 0;\n\t\n\tint len = nums.length;\n\tint[][] dp = new int[len][len];\n\t\n\n\tfor(int i = nums.length - 1; i >= 0; i--) {\t// i represent the left closed idx of str\n\t\tfor(int j = i; j <= nums.length - 1; j++) { // j represent the right closed idx \n\t\t\tfor(int k = i; k <= j; k++) {\n\t\t\t\tint val = 0;\n\t\t\t\tval += (k == i) ? 0 : dp[i][k-1];\n\t\t\t\tval += (k == j) ? 0 : dp[k+1][j];\n\t\n\t\t\t\t// Here is nums[i-1/j+1] instead of nums[k-1/k+1]\n\t\t\t\t// Since ?*nums[k]*? executed at last.\n\t\t\t\tval += ((i==0) ? 1 : nums[i-1]) * nums[k] * ((j==len-1) ? 1 : nums[j+1]);\n\t\t\t\tdp[i][j] = Math.max(dp[i][j], val);\n\t\t\t}\n\t\t}\n\t}\n\treturn dp[0][len-1];\n}\n```\n\n\nDemo:\n```\nusing [3,1,5,8] as an example, direction of i from len-1 to 0.\n\ni=3>=0;\tj=3<=3; max=0; dp[3][3] = max = 40. // [8]\n\t\t\t\tk=3<=3, val=0, val = 5*8*1 = 40.\n\t\t\t\tk=4>3. \ni=2>=0;\tj=2<=3; max=0; dp[2][2] = max = 40. // [5]\n\t\t\t\tk=2<=2, val=0, val = 1*5*8 = 40, update max.\n\t\t\t\tk=3>2. \n        j=3<=3; max=0; dp[2][3] = max = 48. // [5,8]\n\t\t\t\t// delete [3,3] first then delete [2,2]\n\t\t\t\tk=2<=3, val=0, val = 0 + dp[3][3] + 1*5*1 = 40 + 5 = 45, update max.\n\t\t\t\t// delete [2,2] first then delete [3,3]\n\t\t\t\tk=3<=3, val=0, val = dp[2][2] + 0 + 1*8*1 = 40 + 8 = 48, update max.\n\t\t\t\tk=4>3.\n\t    j=4>3.\ni=1>=0;\tj=1<=3; max=0; dp[1][1] = max = 15. // [1]\n\t\t\t\tk=1<=1, val=0, val = 3*1*5 = 15, update max.\n\t\t\t\tk=2>1. \n        j=2<=3; max=0; dp[1][2] = max = 135. // [1,5]\n\t\t\t\t// delete [2,2] first then delete [1,1]\n\t\t\t\tk=1<=2, val=0, val = 0 + dp[2][2] + 3*1*8 = 40 + 24 = 64, update max.\n\t\t\t\t// delete [1,1] first then delete [2,2]\n\t\t\t\tk=2<=2, val=0, val = dp[1][1] + 0 + 3*5*8 = 15 + 120 = 135, update max.\n\t\t\t\tk=3>2.\n        j=3<=3; max=0; dp[1][3] = max = 159. // [1,5,8]\n\t\t\t\t// delete max of [2,3] fist then delete [1,1]\n\t\t\t\tk=1<=3, val=0, val = 0 + dp[2][3] + 3*1*1 = 48 + 3 = 51, update max.\n\t\t\t\t// delete [1,1] and [3,3] first then delete [2,2]\n\t\t\t\tk=2<=3, val=0, val = dp[1][1] + dp[3][3] + 3*5*1 = 15 + 40 + 15 = 70, update max.\n\t\t\t\t// delete max of [1,2] first then delete [3,3]\n\t\t\t\tk=3<=3, val=0, val = dp[1][2] + 0 + 3*8*1 = 135 + 24 = 159, update max.\n\t\t\t\tk=4>3. \n        j=4>3.\ni=0>=0;\tj=0<=3; max=0; dp[0][0] = max = 3. // [3]\n\t\t\t\tk=0<=0, val=0, val = 0 + 0 + 1*3*1 = 3, update max.\n\t\t\t\tk=1>0. \n        j=1<=3; max=0; dp[0][1] = max = 30. // [3,1]\n\t\t\t\t// delete [1,1] first then delete [0,0]\n\t\t\t\tk=0<=1, val=0, val = 0 + dp[1][1] + 1*3*5 = 15 + 15 = 30, update max.\n\t\t\t\t// delete [0,0] first then delete [1,1]\n\t\t\t\tk=1<=1, val=0, val = dp[0][0] + 0 + 1*1*5 = 3 + 5 = 8, update max.\n\t\t\t\tk=2>1.\n        j=2<=3; max=0; dp[0][2] = max = 159. // [3,1,5]\n\t\t\t\t// delete max of [1,2] first then delete [0,0]\n\t\t\t\tk=0<=2, val=0, val = 0 + dp[1][2] + 1*3*8 = 135 + 24 = 159, update max.\n\t\t\t\t// delete [0,0] and [2,2] first then delete [1,1]\n\t\t\t\tk=1<=2, val=0, val = dp[0][0] + dp[2][2] + 1*1*8 = 30 + 40 + 8 = 78, update max.\n\t\t\t\t// delete max of [0,1] first then delete [2,2]\n\t\t\t\tk=2<=2, val=0, val = dp[0][1] + 0 + 1*5*8 = 30 + 40 = 70, update max.\n\t\t\t\tk=3>2.\n        j=3<=3; max=0; dp[0][3] = max = 167. // [3,1,5,8]\n\t\t\t\t// delete max of [1,3] first then delete [0,0]\n\t\t\t\tk=0<=3, val=0, val = 0 + dp[1][3] + 1*3*1 = 159 + 3 = 162, update max.\n\t\t\t\t// delete [0,0] and max of [2,3] first then delete [1,1]\n\t\t\t\tk=1<=3, val=0, val = dp[0][0] + dp[2][3] + 1*1*1 = 3 + 48 + 1 = 52, update max.\n\t\t\t\t// delete max of [0,1] and [3,3] then delete [2,2]\n\t\t\t\tk=2<=3, val=0, val = dp[0][1] + dp[3][3] + 1*5*1 = 30 +_40 + 5 = 75, update max.\n\t\t\t\t// delete max of [0,2] then delete [3,3]\n\t\t\t\tk=3<=3, val=0, val = dp[0][2] + 0 + 1*8*1 =159 + 8 = 167, update max.\n\t\t\t\tk=4>3.\n        j=4>3.\ni=-1<0.\nreturn dp[0][3] = 167.\n\n```\n\n\n\n
['Dynamic Programming', 'Java']