心理教育网站建设目的,网址导航模板,wordpress标签404,wordpress 文章多了戳气球
题目描述
有 n 个气球#xff0c;编号为0 到 n-1#xff0c;每个气球上都标有一个数字#xff0c;这些数字存在数组 nums 中。
现在要求你戳破所有的气球。如果你戳破气球 i #xff0c;就可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 …戳气球
题目描述
有 n 个气球编号为0 到 n-1每个气球上都标有一个数字这些数字存在数组 nums 中。
现在要求你戳破所有的气球。如果你戳破气球 i 就可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后气球 left 和气球 right 就变成了相邻的气球。 求所能获得硬币的最大数量。
输入格式
输入的第一行包含N 之后给出由 N 个数字组成的序列 nums。
输出格式
一个整数为所能获得硬币的最大数量。
样例输入
4 3 1 5 8
样例输出
167
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scannernew Scanner(System.in);int n scanner.nextInt();int []pointsnew int[n2];int [][]dpnew int[n2][n2];points[0]1;points[n1]1;for (int i0;in;i){points[i1]scanner.nextInt();}for(int in;i0;--i){//从下到上遍历dp数组for(int ji1;jn2;j){//从左到右遍历dp数组for(int ki1;kj;k){dp[i][j]Math.max(dp[i][j],dp[i][k]dp[k][j]points[i]*points[k]*points[j]);}}}System.out.println(dp[0][n1]);}
}
