算法题 吹气球 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
	}
}

本文地址：https://blog.csdn.net/qq_37904407/article/details/108936305