6449. 收集巧克力 (opens new window)

1.枚举+贪心

分析：同种类型的巧克力通过移动，总共可以有nums.length种可能的成本价格。换而言之，整个成本数组可以移动的最大轮次为nums.length。移动最后一次后，每种类型的巧克力成本又恢复初始状态，而此时总价和初始状态相比还多了移动的成本价。因此最小成本总价一定是在前num.length-1次移动中。

假设当前移动了i次，用哈希保存每种类型巧克力在前i次移动中最小的成本价格(这里保存的是最小成本价对应的轮次)。每轮移动的总成本底价为round * x，round为轮次，x为移动一次的成本。采用贪心策略，每种巧克力成本价只选前i次搜索中的最小值，加入到当前轮次的总价计算中。

此处不需要考虑在当前轮次中是否出现至少一种类型巧克力的最小成本，因为在前面的轮次中已经被计算过，因此通过这种搜索策略不会错过最优方案。

class Solution {
    public long minCost(int[] nums, int x) {
       long res=Long.MAX_VALUE;
        Map<Integer,Integer> map=new HashMap<>();
        //i:轮次
        for(int i=0;i<nums.length;i++){
            long sum=(long)i*x;
            //j:元素下标
            for(int j=0;j<nums.length;j++){
                if(i==0){
                    map.put(j,0);
                    sum=sum+(long)nums[j];
                }
                else{
                    int minrounds=map.get(j);
                    long minprice=j-minrounds>=0?nums[j-minrounds]:nums[nums.length-(minrounds-j)];
                    long currprice=j-i>=0?nums[j-i]:nums[nums.length-(i-j)];
                    sum+=Math.min(currprice,minprice);
                    if(currprice<minprice){
                        map.put(j,i);
                    }
                }
            }
            res=Math.min(res,sum);
        }
        return res;
    }
}