演演算法題 吹氣球 javascript

描述

有n個氣球，編號為0到n-1，每個氣球都有一個分數，存在nums陣列中。每次吹氣球i可以得到的分數為 nums[left] * nums[i] * nums[right]，left和right分別表示i氣球相鄰的兩個氣球。當i氣球被吹爆後，其左右兩氣球即為相鄰。要求吹爆所有氣球，得到最多的分數。

樣例

樣例1

輸入：[4, 1, 5, 10]
輸出：270
解釋：
nums = [4, 1, 5, 10] 吹爆 1, 得分 4 * 1 * 5 = 20
nums = [4, 5, 10] 吹爆 5, 得分 4 * 5 * 10 = 200
nums = [4, 10] 吹爆 4, 得分 1 * 4 * 10 = 40
nums = [10] 吹爆 10, 得分 1 * 10 * 1 = 10
總得分 20 + 200 + 40 + 10 = 270

樣例2

輸入：[3,1,5]
輸出：35
解釋：
nums = [3, 1, 5] 吹爆 1, 得分 3 * 1 * 5 = 15
nums = [3, 5] 吹爆 3, 得分 1 * 3 * 5 = 15
nums = [5] 吹爆 5, 得分 1 * 5 * 1 = 5
總得分 15 + 15 + 5 = 35

const maxCoins = function(nums) {
        let n = nums.length;
        let dp = createArrTwo(n+2,n+2);
        let visit = createArrTwo(n+2,n+2);
        let arr = new Array(n+2);
        for(let i = 1;i <= n; ++i){
            arr[i] = nums[i-1];
        }
        arr[0] = 1;
        arr[n+1] = 1;
        
        return reBalloon(arr,dp,visit,1,n);
    function reBalloon(arr,dp,visit,left,right){//遞迴函數
        if(visit[left][right] == 1)
            return dp[left][right];
        
        let sum = 0;
        for(let x = left;x <= right;++x){
            let midValue = arr[left - 1] * arr[x] * arr[right + 1];
            let leftValue = reBalloon(arr,dp,visit,left,x-1);
            let rightValue = reBalloon(arr,dp,visit,x + 1,right);
            sum = Math.max(sum,leftValue + midValue + rightValue);
        }
        visit[left][right] = 1;
        dp[left][right] = sum;
        return sum;
    }
    
	function createArrTwo(num1,num2){//建立二維陣列
		let arr = new Array(num1)
		for (let i = 0; i < num1; ++i) {
			arr[i] = new Array(num2)
		}
		return arr
	}
}