能量项链

C++ 解法, 执行用时: 5ms, 内存消耗: 636KB, 提交时间: 2022-08-03

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param num int整型vector 
     * @return int整型
     */
    int necklace(int n, vector<int>& num) {
        // write code here
        int n2 = n << 1;
        const int mod = 1000000007;
        vector<int> nums(n2, 0);
        for(int i = 0; i < n; ++ i){
            nums[i] = num[i];
            nums[i + n] = num[i];
        }
        vector<vector<int>> dp(n2, vector<int>(n2, 0));
        for(int l = 1; l < n; ++ l){
            for(int i = 0; i + l < n2; ++ i){
                int j = i + l;
                for(int k = i; k < j; ++ k){
                    dp[i][j] = max(dp[i][j], (dp[i][k] + dp[k + 1][j] + nums[i]*nums[k + 1]* nums[j + 1]) % mod);
                }
            }
        }
        int res = 0;
        for(int i = 0; i < n; ++ i){
            res = max(dp[i][i + n - 1], res);
        }
        return res;
    }
};

C 解法, 执行用时: 6ms, 内存消耗: 420KB, 提交时间: 2022-06-23

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @param num int整型一维数组 
 * @param numLen int num数组长度
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

int max(int a, int b) {
    return a > b ? a : b;
}

int necklace(int n, int* num, int numLen ) {
    int start[2 * n + 1];
    for (int i = 0; i < n; i++) {
        start[i] = num[i];
        start[i+n] = start[i];
    }
    start[2 * n] = start[0];
    
    int **dp = (int **)malloc(sizeof(int *) * 2 * n);
    for (int i = 0; i < 2 * n; i++) {
        dp[i] = (int *)malloc(sizeof(int) * n);

        memset(dp[i], 0, sizeof(int) * n);
    }
    
    int maxPower = 0;
    for (int d = 1; d < n; d++) {
        for (int i = 0; i < 2 * n - d; i++) {
            for (int k = 0; k < d; k++) {
                dp[i][d] = max(dp[i][d], 
                               (dp[i][k] + dp[i+k+1][d-k-1] + start[i] * start[i+k+1] * start[i+d+1]) % 1000000007);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        maxPower = max(maxPower, dp[i][n-1]);
    }
    
    for (int i = 0; i < 2 * n; i++) {
        free(dp[i]);
    }
    free(dp);
    
    return maxPower;
}

Java 解法, 执行用时: 48ms, 内存消耗: 10908KB, 提交时间: 2022-06-22

import java.util.*;
 
 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @param num int整型ArrayList
     * @return int整型
     */
    public int necklace (int n, ArrayList<Integer> num) {
//        dp48
        int e9 = 1000000007, j, index = 0;
        int res = 0, n2 = n << 1;
        int[] nums = new int[n2 + 1];
        for (Integer o : num) {
            nums[index] = o;
            nums[index++ + n] = o;
        }
        int[][] dp = new int[n2][n2];
        /**
         * 这里为什么用long再取模结果不对啊
         * dp[i][k] + dp[k + 1][j] + nums[i] * nums[k + 1] * nums[j + 1] 感觉这3个数相加有可能超出int长度吧
         * long[][] dp = new long[n2][n2];
         */
        //枚举长度
        for (int l = 1; l < n; l++) {
            //枚举起点
            for (int i = 0; i + l < n2; i++) {
                //由起点推导终点
                j = i + l;
                //枚举由k到j的每个分割点 枚举决策
                for(int k = i; k < j; k++) {
                    //状态转移方程
                    dp[i][j] = Math.max(dp[i][j], (dp[i][k] + dp[k + 1][j] + nums[i] * nums[k + 1] * nums[j + 1]) % e9);
                }
            }
        }
        //枚举可能的答案
        for(int i = 0; i < n; i++){
            res = Math.max(dp[i][i + n - 1], res);
        }
        return res;
    }
}

Java 解法, 执行用时: 49ms, 内存消耗: 10756KB, 提交时间: 2022-06-23

import java.util.*;
import java.lang.*;

class Solution {
    public int necklace (int n, ArrayList<Integer> num) {
        int mod = 1000000007, j, f = 0;
        int z = 0, m = n << 1;
        int[] c = new int[m + 1];
        for (Integer o : num) {
            c[f] = o;
            c[f++ + n] = o;
        }

        int[][] a = new int[m][m];
        for (int l = 1; l < n; l++) {
            for (int i = 0; i + l < m; i++) {
                j = i + l;
                for (int k = i; k < j; k++) {
                    a[i][j] = Math.max(a[i][j],
                                       (a[i][k] + a[k + 1][j] + c[i] * c[k + 1] * c[j + 1]) % mod);
                }
            }
        }
        for (int i = 0; i < n; i++) {
            z = Math.max(a[i][i + n - 1], z);
        }
        return z;
    }
}

Java 解法, 执行用时: 50ms, 内存消耗: 10840KB, 提交时间: 2022-07-31

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param num int整型ArrayList 
     * @return int整型
     */
    public int necklace (int n, ArrayList<Integer> num) {
        // write code here
        
        int mod = 1000000007, j, f = 0;
        int z = 0, m = n << 1;
        int[] c = new int[m + 1];
        for (Integer o : num) {
            c[f] = o;
            c[f++ + n] = o;
        }
 
        int[][] a = new int[m][m];
        for (int l = 1; l < n; l++) {
            for (int i = 0; i + l < m; i++) {
                j = i + l;
                for (int k = i; k < j; k++) {
                    a[i][j] = Math.max(a[i][j],
                                       (a[i][k] + a[k + 1][j] + c[i] * c[k + 1] * c[j + 1]) % mod);
                }
            }
        }
        for (int i = 0; i < n; i++) {
            z = Math.max(a[i][i + n - 1], z);
        }
        return z;
    }
}

详情