首页 > 试题广场 >

合并金币

[编程题]合并金币

热度指数：1771 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有 N 堆金币排成一排，第 i 堆中有 C[i] 块金币。每次合并都会将相邻的两堆金币合并为一堆，成本为这两堆金币块数之和。经过N-1次合并，最终将所有金币合并为一堆。请找出将金币合并为一堆的最低成本。

其中，1 <= N <= 30，1 <= C[i] <= 100

输入描述:

第一行输入一个数字 N 表示有 N 堆金币
第二行输入 N 个数字表示每堆金币的数量 C[i]

输出描述:

输出一个数字 S 表示最小的合并成一堆的成本

示例1

输入

4
3 2 4 1

输出

示例2

输入

30
10 20 30 40 50 60 70 80 90 100 99 89 79 69 59 49 39 29 19 9 2 12 22 32 42 52 62 72 82 92

输出

算法知识视频讲解

死命令

/**手动模拟最小情况，发现关键就是在确定区间，确定分割点*/ 已AC

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] money = new int[n+1];
        int[] preSum = new int[n+1];
        for(int i = 1; i <= n; i++){
            money[i] = sc.nextInt();
            if(i == 1) preSum[i] = money[i];
            else preSum[i] = preSum[i-1] + money[i];
        }
        sc.close();
        
        int[][] dp = new int[n + 1][n + 1];
        for(int len = 2; len <= n; len++){
            for(int i = 1; i <= n - len + 1; i++){
                int j = i + len - 1;
                dp[i][j] = Integer.MAX_VALUE;
                int sum = preSum[j] - preSum[i - 1];
                for(int k = i; k < j; k++){
                    dp[i][j] = Math.min(dp[i][j],dp[i][k] + dp[k + 1][j] + sum);
                }
            }
        }
        System.out.println(dp[1][n]);
    }
}

发表于 2020-03-16 12:58:44 回复(3)

hskxhjd

区间DP + 前缀和

#include <bits/stdc++.h>
using namespace std;

const int N = 31;
int a[N], s[N];
int f[N][N];
int n;

int main(){
    memset(f, 0x3f, sizeof f);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i], s[i] = s[i - 1] + a[i], f[i][i] = 0;    // 初始化

    for (int len = 2; len <= n; len++){//枚举区间长度
        for (int i = 1; i + len - 1 <= n; i++){//枚举起点
            int j = i + len - 1;    // 终点
            for (int k = i + 1; k <= j; k++){    // 计算[i, j]最小代价
                f[i][j] = min(f[i][j], f[i][k - 1] + f[k][j] + s[j] - s[i - 1]);
            }
        }
    }

    cout << f[1][n] << endl;
    return 0;
}

发表于 2022-05-17 13:53:07 回复(0)

牛客279675892号

public static void main(String[] args) {
    Scanner in = new Scanner(System.in); int n = in.nextInt(); int[] jinbi = new int[n]; int[] sum = new int[n]; for(int i=0;i<n;i++) {
        jinbi[i] = in.nextInt(); if(i==0) sum[i]=jinbi[i]; else sum[i]=sum[i-1]+jinbi[i];
    }
    in.close(); long temp = 0; long min =0; long[][] dp = new long[n][n]; for(int l=1;l<n;l++) { for(int i=0;i<n&&i+l<n;i++) {
            min = dp[i][i]+dp[i+1][i+l]; for(int k=i+1;k<=i+l-1;k++) {
                temp = dp[i][k] + dp[k+1][i+l]; if(temp<min) min = temp;
            } if(i>0)
                dp[i][i+l]=min+sum[i+l]-sum[i-1]; else  dp[i][i+l]=min+sum[l];
        }
    }
    System.out.println(dp[0][n-1]); for(int i =0;i <n;i++){ for(int j = 0;j<n;j++){
            System.out.print(dp[i][j] + " ");
        }
        System.out.println();
    }
}

发表于 2020-03-11 14:33:58 回复(0)

未命名。555

N = int(input())
C = list(map(int,input().split(' ')))

dp = [[0 for _ in range(N)] for _ in range(N)]

for i in range(N-1):
    dp[i][i+1] = C[i]+C[i+1]

for i in range(N-1)[::-1]:
    for j in range(i+2, N):
        dp[i][j] = dp[i][i] + dp[i+1][j] + sum(C[i:j+1])
        for k in range(i+1, j):
            dp[i][j] = min(dp[i][k]+dp[k+1][j] + sum(C[i:j+1]), dp[i][j])


print(dp[0][-1])

编辑于 2020-03-11 11:01:38 回复(0)

菲尼克斯弗兰克

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n+1];
        int[] pre = new int[n+1];
        for (int i = 1; i <= n; i++) {
            arr[i] = in.nextInt();
            pre[i] = pre[i-1] + arr[i];
        }
        fun(arr, pre, n);
        in.close();
    }

    // 合并金币-动态规划
    // dp[i][j] 表示第i堆到第j堆合并的代价和
    // base case: dp[x][x] = 0
    // 方程:dp[i][j] = dp[i][k]+dp[k+1][j]+cost
    // 计算顺序: 从下到上 从左到右
    public static void fun(int[] arr, int[] pre, int n) {
        int[][] dp = new int[n+1][n+1];
        // i是左边界 j是右边界 k是分割点
        // 注意枚举时的取值问题
        for (int i = n; i > 0; i--) {
            for (int j = i+1; j <= n; j++) {
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = i; k < j; k++) {
                    int cost = pre[j] - pre[i-1];
                    dp[i][j] = Math.min(dp[i][k] + dp[k+1][j] + cost, dp[i][j]);
                }
            }
        }
        System.out.println(dp[1][n]); // 结果是从1合并到n的代价
    }
}

发表于 2022-08-16 18:29:46 回复(0)

寻找任大侠

dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + sumIJ);

以k为分界点，算出[i~k]的代价+[k+1~j]的代价，最后的sum[i~j]代表的是，把这两堆合并的代价。注意题目的意思，这里的代价是累加的过程。

发表于 2022-05-08 15:36:29 回复(0)

C/C++

融入蔚蓝

#include<iostream>
#include<vector>
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    const int size = n;
    vector<int> C(size);
    int x;
    for(int i=0; i<size; ++i)
    {
        cin>>x;
        C[i] = x;
    }
    if(size == 1) { cout<<0; return 0; }
    vector<vector<int>> dp(size, vector<int>(size, 0));
    for(int i=size-1; i>=0; --i)
    {
        for(int j=i+1; j<size; ++j)
        {
            int _min = INT_MAX;
            for(int k=i; k<j; ++k)
            {
                _min = min(_min, dp[i][k]+dp[k+1][j]);
            }
            for(int p=i; p<=j; ++p) {dp[i][j]+=C[p];}
            dp[i][j] += _min;
        }
    }
    cout << dp[0][size-1] << endl;
    return 0;
}

编辑于 2022-03-04 20:05:32 回复(0)

美年达1999

https://leetcode-cn.com/problems/minimum-cost-to-merge-stones/solution/yi-dong-you-yi-dao-nan-yi-bu-bu-shuo-ming-si-lu-he/

//动态规划

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] stones = new int[n];
        for(int i = 0; i < n; i++){
            stones[i] = sc.nextInt();
        }
        sc.close();
        //动态规划dp[i][j]=min(dp[i][k]+dp[k+1][j]+sum[j]-sum[i]);
        int[][] dp=new int[stones.length][stones.length];
        int[] sum=new int[stones.length+1];
        for(int i=1;i<stones.length+1;i++){
            sum[i]=sum[i-1]+stones[i-1];
            //dp[i-1][i-1]=stones[i-1];
        }
        for(int i=stones.length-1;i>=0;i--){
            for(int j=i+1;j<stones.length;j++){
                dp[i][j]=Integer.MAX_VALUE;
                for(int k=i;k<j;k++){
                    dp[i][j]=Math.min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j+1]-sum[i]);
                }
            }
        }
       System.out.println(dp[0][n-1]);
    }
}

发表于 2021-02-25 16:58:31 回复(0)

小贱贱XJJ

石子堆问题，使用动态规划 dp[i][j] 表示i 到j 合并的最低成本

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = Integer.parseInt(scanner.nextLine());
        int[] arr = new int[n];
        for (int i = 0; i < n ; i++) {
            arr[i] = scanner.nextInt();
        }
        System.out.println(minCombination(arr));

    }

    private static int minCombination(int[] arr) {
        int n = arr.length;
        int[][] sum = new int[n + 1][n + 1];
        int[][] dp = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i][i] = 0;
            sum[i][i] = arr[i - 1];
        }
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                sum[i][j] = sum[i][j - 1] + sum[j][j];
            }
        }
        for (int len = 1; len < n; len++) { //区间长度
            for (int i = 1; i + len <= n; i++) {  //区间开始
                int j = i + len;  //区间结尾
                for (int k = i; k < j; k++) {
                    if(dp[i][j] == 0){   //确保dp[i][j]的更新
                        dp[i][j] = dp[i][k] + dp[k + 1][j] + sum[i][j];
                    }else{
                        dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[i][j]);
                    }
                }
            }
        }
        return dp[1][n];
    }
}

发表于 2020-10-25 14:17:39 回复(0)

冲鸭冲鸭呼啦啦

#include<iostream> //区间动态规划
#include<vector>
#include<climits>
#include<algorithm>
using namespace std;
int main()
{
int N;
cin>>N;
vector<int> c(N);
vector<vector<int>> f(N,vector<int>(N,INT_MAX)); //存放结果，f[i][j]表示从下标i堆到下标j堆的最小成本
vector<int> sum(N); //存放当前金币和，用于bp计算
for(int i=0;i<N;i++)
{
cin>>c[i];
f[i][i]=0; //对角线初始化为0，其余为INT_MAX
if(i==0)
sum[i]=c[i];
else sum[i] = sum[i - 1]+c[i];
}
for(int len=1;len<=N;len++) //枚举长度，长度为1表示本身
{
for(int j=0;j+len<N+1;j++) //枚举起点
{
int end=j+len-1; //计算终点
for(int i=j;i<end;i++) //枚举分割点
f[j][end]=min(f[j][end],f[j][i]+f[i+1][end]+sum[end]-sum[j]+c[j]);
}
}
cout<<f[0][N-1]<<endl;
return 0;
}

发表于 2020-08-13 10:41:20 回复(0)

牛客85741140号

length = int(input())
coins = list(map(int, input().split()))
dp = [[float("inf")] * length for _ in range(length)]
for i in range(length - 1, -1, -1):
    for j in range(i, length):
        if i == j:
            dp[i][j] = 0
        else:
            curSum = sum(coins[i: j + 1])
            for k in range(i, j):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + curSum)

print(dp[0][-1])

发表于 2020-07-19 17:50:43 回复(0)

kkyyy

哈夫曼树变形题

发表于 2020-07-02 18:23:36 回复(0)

fibonaccii

#include <iostream>
#include <algorithm>
#include <vector>
#include <limits.h>

class Solution{ 
public:
  template<typename T> using Matrix = std::vector<std::vector<T>>;

  static void solve(const std::vector<int>& data, int length) {
    int N = length;
    
    Matrix<int> dp(N+1, std::vector<int>(N+1, INT_MAX));
    Matrix<int> sum(N+1, std::vector<int>(N+1));

    // 初始化,basecase
    for(int i=1; i <= N; ++i) { 
      sum[i][i] = data[i];
      dp[i][i] = 0;
    }

    for(int interval=1; interval < N; ++interval) {   // 区间长度
      // 对于同一个区间长度，不同起点，寻找最小的相邻的两堆
      // 区间最大的终点是数组的最后一个元素 index：N
      for(int begin=1; begin + interval <= N; ++begin) { // 区间起点
        int end = begin + interval;                      // 区间终点 

        /*** @brief: 思路，在区间[begin, end]找到和最小的两个，加起来，作为 dp[begin][end]的值
         * 
         * 
         * 动态方程解释：dp[begin][k] + dp[k+1][end] + sum[begin][end]
         *     因为之前合并成 [begin][k]、[k+1][end]这两堆所需的代价，
         *     将他们合并成新的堆，所需的代价，就需要在此基础上加上新的和: sum[begin][end]
         * 
         *  dp[begin][end] = std::min(dp[begin][end], dp[begin][k] + dp[k+1][end] + sum[begin][end]);
         * 
         * 就是为了找个最小值：相同的区间长度，不同的起点。
         * 
         */
        
        for(int k=begin; k < end; ++k) {
          sum[begin][end] = sum[begin][k] + sum[k+1][end];
          dp[begin][end] = std::min(dp[begin][end], dp[begin][k] + dp[k+1][end] + sum[begin][end]);
        }
      }
    }

    std::cout<< dp[1][N]<<std::endl;
  }
};


int main(int argc, char const *argv[]) {

  int N;
  std::cin>>N;
  std::vector<int> data(N+1, 0);

  for(int i =1; i <= N; ++i) { 
     std::cin>> data[i];
  }

  Solution::solve(data, N);
  return 0;
}

发表于 2020-06-04 10:41:38 回复(0)

C/C++

迷路的offer

#include<vector>
(721)#include<iostream>
#include<algorithm>
using namespace std;
int minGold(const vector<int>golds) {
	if (golds.size() == 1)return 0;
	vector<int>sums(golds.size());
	for (int i = 0; i < golds.size(); ++i) {
		sums[i] = golds[i];
		if (i != 0)
			sums[i] += sums[i - 1];
	}
	vector<vector<int>>dp;
	for (int i = 0; i < golds.size(); ++i) {
		dp.emplace_back(golds.size(), 0);
	}
	for (int i = golds.size()-1; i >=0; --i) {
		for (int j = i; j < golds.size(); ++j) {
			if (i == j)
				dp[i][j] =0;
			else{
				int tmp = INT32_MAX;
				for (int k = i; k < j; ++k) {
					tmp = min(tmp, dp[i][k] + dp[k + 1][j] + sums[j] - sums[i] + golds[i]);
				}
				dp[i][j] = tmp;
			}
		}
	}
	return dp[0][golds.size()-1];
}
int main() {
	int num;
	cin >> num;
	vector<int>nums(num);
	for (int i = 0; i < num; ++i)
		cin >> nums[i];
	cout << minGold(nums) << endl;
}

发表于 2020-05-12 20:54:23 回复(0)

降龙尊者

思路分析:

比如我们要算第i个到第j个的成本F(i, j), 我们最后一步肯定是把两个小堆叠起来得到的

用k来标记划分点的下标, 则第一个小堆成本为F(i, k), 第二个小堆成本为F(k+1, j), 新的成本为sum(i, j)

所以有 F(i, j) = min(F(i, k) + F(k+1, j) + sum(i, j) 其中要遍历k

发表于 2020-04-22 20:16:49 回复(0)

lm77

解题思路就是，求相邻两个和最小的，第一次合并，将合并后的与最初的数在一个集合中，继续找最小的，一直递归求和，求出最小合并

发表于 2020-04-21 17:52:04 回复(8)

Karn

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        mergeCoins();
    }
     
    private static void mergeCoins() {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        int[] sum = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
            sum[i] = i == 0 ? arr[i] : arr[i] + sum[i - 1];
        }
        int[][] dp = new int[n][n];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if(i == j)
                    dp[i][j] = 0;
                else if(i + 1 == j)
                    dp[i][j] = arr[i] + arr[j];
                else {
                    dp[i][j] = Integer.MAX_VALUE;
                    int sumIJ = i == 0 ? sum[j] : sum[j] - sum[i - 1];
                    for (int k = i; k < j; k++) {
                        dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + sumIJ);
                    }
                }
            }
        }
        System.out.println(dp[0][n - 1]);
    }
}

dp[i][j]: 合并 [i, j] 间所有的堆（包括堆 i 与堆 j）需要花费的最小代价

发表于 2020-03-24 20:15:10 回复(1)

牛客628558444号

package test;

import java.util.Arrays;
import java.util.Scanner;

public class Test01 {
    /**
     * 有 N 堆金币排成一排，第 i 堆中有 C[i]块金币。每次合并都会将相邻的两堆金币合并为一堆，成本为这两堆金币块数之和。
     * 经过N-1次合并，最终将所有金币合并为一堆。请找出将金币合并为一堆的最低成本。
     *
     * 其中，1 <= N <= 30，1 <= C[i] <= 100
     */
    public static void main(String[] args) {
        // 接受数据
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if (n != 1) {
            int[] c = new int[n];
            for (int i = 0; i < c.length; i++) {
                c[i] = sc.nextInt();
            }
            sc.close();
            //计算总花费money
            int money=0;
            int monOne=0;//一次花费

            for(int i=0;i<c.length-1;i++) {
                //每次让最小的两位数相加
                Arrays.sort(c);//从小到大自动排序
                monOne=c[0]+c[1];
                c[0]=101;
                c[1]=monOne;
                money = money+monOne;
            }
            System.out.println(money);
        } else {
            System.out.println(0);
        }

    }
}

发表于 2020-03-12 11:53:45 回复(4)