阿里云3.24笔试第三题

自己用的二维dp超内存了，正确应该是贪心

import java.util.*;

public class Aliyun324_3 {

    public static void main(String[] args) {
        //阿里云3.24笔试 第三题
        //n个城市，从1号城市到n号城市，每到达一个城市消耗1单位粮食
        //输入n个数，表示每个城市粮食的单价。粮食无上限
        //可以携带额外的的粮食，在移动时超过1单位的额外粮食要支付运费，每单位支付1
        //求最小的支付金额

        //输入示例
        //4
        //1 3 2 4
        //输出：5
        //贪心做法： dp[i] = dp[i - 1] + Math.min(i - 1 - j + prices[j]) 对于：1 <= j <= i - 1
        //贪心的地方在于对于i处，要选取之前城市中的价格最低的（包含上运费）
        //dp[i]表示到达城市i所需要的最小花费
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] prices = new int[n + 1];
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            prices[i] = in.nextInt();
        }
        for (int i = 2; i <= n; i++) { //从第二个城市开始
            int minVal = Integer.MAX_VALUE;
            for (int j = 1; j <= i - 1; j++) { //检索第i个城市之前的最小花费，运费是i-1-j
                minVal = Math.min(minVal, i - 1 - j + prices[j]);
            }
            dp[i] = dp[i - 1] + minVal;
        }
        System.out.println(dp[n]);
    }
}