Summary: Input size / sub-problem size / sub-problem complexity / time complexity / space complexity
Category 1.1
|
1 2 3 4 5 6 |
Input: O(n) Sub-problems: O(n) Each sub-problem depends on O(1) smaller problems Time complexity: O(n) Space complexity: O(n) -> O(1) dp[i] := solution of A[1->i] // prefix |
Template
|
1 2 3 4 |
dp = new int[n + 1] for i = 1 to n: dp[i] = f(A[i], dp[i-1], dp[i-2], ...) return dp[n] |
Summary and slides
