java对于这种自下而上的记忆化问题,运行时的大O是什么?
我目前正在解决一个问题,并想出了一个解决方案。然而,我需要帮助计算这个问题的运行时复杂性
问题链接:https://algo.monster/problems/minimum_total_container_size
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;
import java.util.HashMap;
class Solution {
public static int minContainerSize(List<Integer> boxSizes, int days) {
// WRITE YOUR BRILLIANT CODE HERE
HashMap<String, Integer> memo = new HashMap<>();
return recursive(boxSizes, days, 0, memo);
}
public static int recursive(List<Integer> boxSizes, int days, int currentIndex, HashMap<String, Integer> memo) {
int currentMax = 0;
int minimumSize = Integer.MAX_VALUE;
String key = days + "|" + currentIndex;
if(memo.containsKey(key)) return memo.get(key);
if(days == 1) {
for(int i = currentIndex; i < boxSizes.size(); i++) {
currentMax = Math.max(currentMax, boxSizes.get(i));
}
task return currentMax;
}
for(int i = currentIndex; i < boxSizes.size() - days + 1; i++) {
currentMax = Math.max(boxSizes.get(i), currentMax);
minimumSize = Math.min(recursive(boxSizes, days-1, i+1, memo) + currentMax, minimumSize);
}
memo.put(key, minimumSize);
return memo.get(key);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
List<Integer> boxSizes = Arrays.stream(scanner.nextLine().split(" ")).map(Integer::parseInt).collect(Collectors.toList());
int days = Integer.parseInt(scanner.nextLine());
scanner.close();
int res = minContainerSize(boxSizes, days);
System.out.println(res);
}
}
以下是我认为的运行时:
- 如果我们不添加备注,这个问题就是一个回溯。
-如果没有备忘录,运行时间应该是O(N^天)
式中,as N是盒子大小的长度和天数。 -有了备忘录, O(天*N)李>
如果我错了,请纠正我
共 (0) 个答案