0%

leetcode每日一题-戳气球

Posted on In ,

戳气球

image1

##1.分治+记忆化搜索

首先需要在数组两端加一个虚拟边界，为此将原数组拷贝到新数组val中，其中val[0]=val[n+1]=1。可以这么想这个问题，即只考虑在$(i,j)$之间戳破最后一个气球，我们令$solve(i,j)$记为将开区间$(i,j)$内的位置全部戳破气球能够得到的最多硬币数。因为戳破的是最后一只气球，那么两端的气球编号就是$i$和$j$，分别对应val[i]和val[j]。

  • $i >= j-1$，那么$solve(i,j)$为0。
  • $i<j-1$，我们枚举$(i,j)$之间的所有位置$mid$，此时$solve(i,j) = solve(i,mid)+solve(mid,j)+val[i]val[j]val[mid]$。我们只要找出值最大的一种情况就好。

为了重复计算，我们可以存储$solve$的结果。

1
class Solution {
2
    int[][] memo;
3
    int[] val;
4
    public int maxCoins(int[] nums) {
5
        int n = nums.length;
6
        val = new int[n+2];
7
        memo = new int[n+2][n+2];
8
        for(int i=1; i<=n; i++){
9
            val[i] = nums[i-1];
10
        }
11
        val[0] = val[n+1] = 1;
12
        for(int i=0; i<=n+1; i++){
13
            Arrays.fill(memo[i], -1);
14
        }
15
        return solve(0, n+1);
16
    }
17
18
    public int solve(int left, int right){
19
        if(left >= right-1){
20
            return 0;
21
        }
22
        if(memo[left][right] != -1){
23
            return memo[left][right];
24
        }
25
        for(int i=left+1; i<right; i++){
26
            int sum = val[left] * val[right] * val[i];
27
            sum += solve(left, i) + solve(i, right);
28
            memo[left][right] = Math.max(memo[left][right], sum); 
29
        }
30
        return memo[left][right];
31
    }
32
}

复杂度分析：

  • 时间复杂度：$O(n^3)$。
  • 空间复杂度：$O(n^2)$。

2.动态规划

思路和方法一一样，令$dp[i][j]$为戳破开区间$(i,j)$最后一只气球能得到的最多的硬币数，边界条件是$i>=j-1$，此时$dp[i][j]=0$。当$i<j-1$时，转移方程为$dp[i][j] = max(dp[i][k]+dp[k][j]+val[i]val[j]val[k])$。其中$k\in[i+1,j-1]$。最终答案就是$dp[0][n+1]$。

1
class Solution {
2
    int[][] memo;
3
    int[] val;
4
    public int maxCoins(int[] nums) {
5
        int n = nums.length;
6
        val = new int[n+2];
7
        memo = new int[n+2][n+2];
8
        for(int i=1; i<=n; i++){
9
            val[i] = nums[i-1];
10
        }
11
        val[0] = val[n+1] = 1;
12
        for(int i=n-1; i>=0; i--){
13
            for(int j=i+2; j<=n+1; j++){
14
                for(int k=i+1; k<j; k++){
15
                    int sum = val[i]*val[j]*val[k];
16
                    sum += memo[i][k] + memo[k][j];
17
                    memo[i][j] = Math.max(memo[i][j], sum);
18
                }
19
            }
20
        }
21
        return memo[0][n+1];
22
    }
23
}

复杂度分析：

  • 时间复杂度：$O(n^3)$。
  • 空间复杂度：$O(n^2)$。