Note: This problem is part of the Atcoder Educational Dp Contest
Problem Link
Brute-Force/Recursive Approach
We know that from given h[i], we can only go to either h[i+1] or h[i+2]. If we reverse this logic, we can see that from any given h[i], we can only arrive there either from h[i-1] or h[i-2]. Finally, the cost of arriving at h[0] is 0 (since we are already there when we start) and the cost for h[1] is |h[1] - h[0]| since we can only come to h[1] from h[0]
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include <bits/stdc++.h>
using namespace std;
int recursive(vector<int> &h, int i)
{
if (i == 0)
return 0;
if (i == 1)
return abs(h[1] - h[0]);
return min(abs(h[i] - h[i - 1]) + recursive(h, i - 1),
abs(h[i] - h[i - 2]) + recursive(h, i - 2));
}
int main()
{
int n;
cin >> n;
vector<int> h(n);
for (int i = 0; i < n; ++i)
cin >> h[i];
cout << recursive(h, n-1);
return 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| n = int(input())
nums = list(map(int, input().strip().split()))
def recursive(nums):
n = len(nums)
def helper(index):
if index == 0:
return 0
if index == 1:
return abs(nums[1] - nums[0])
return min(abs(nums[index] - nums[index - 1]) + helper(index - 1),
abs(nums[index] - nums[index - 2]) + helper(index - 2))
return helper(n - 1)
print(recursive(nums))
|
Complexity Analysis
- Time complexity: $\boldsymbol{O(2^n)}$ - Size of recursion tree will be $2^n$
- Space complexity: $\boldsymbol{O(n)}$ - The depth of the recursion tree can go up to $n$.
Recursive (Top-down) + Memoization
Here, we cache the results of the recursive brute-force approach to reduce time complexity:
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| #include <bits/stdc++.h>
using namespace std;
int topdown(vector<int> &h, int i)
{
static vector<int> dp(h.size(), -1);
if (dp[i] != -1)
return dp[i];
if (i == 0)
return dp[i] = 0;
if (i == 1)
return dp[i] = abs(h[1] - h[0]);
return dp[i] = min(abs(h[i] - h[i - 1]) + topdown(h, i - 1),
abs(h[i] - h[i - 2]) + topdown(h, i - 2));
}
int main()
{
int n;
cin >> n;
vector<int> h(n);
for (int i = 0; i < n; ++i)
cin >> h[i];
cout << topdown(h, n-1);
return 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| n = int(input())
nums = list(map(int, input().strip().split()))
def topDown(nums):
n = len(nums)
dp = [-1] * n
dp[0] = 0
dp[1] = abs(nums[1] - nums[0])
def helper(index):
if index < 0:
return math.inf
if dp[index] != -1:
return dp[index]
dp[index] = min(abs(nums[index - 1] - nums[index]) + helper(index - 1),
abs(nums[index - 2] - nums[index]) + helper(index - 2))
return dp[index]
return helper(n - 1)
print(topDown(nums))
|
Complexity Analysis
Time complexity: $\boldsymbol{O(n)}$ - This is because the recursive function will only branch or call other recursive functions if it hasn’t cached the query yet. The number of possible calls is $n$ (We have to explore each stone)
Space complexity: $\boldsymbol{O(n)}$ - We are caching $n$ results in our DP array and size of recursive stack is also at worst $n$.
Bottom-Up (Tabular)
From the recurrence relation, we can come up with the bottom up approach:
1
2
3
4
5
6
7
8
| Base cases:
if (i == 0)
return dp[i] = 0;
if (i == 1)
return dp[i] = abs(h[1] - h[0]);
Recurrence Relation:
dp[i] = min(abs(h[i] - h[i - 2]) + dp[i - 2], abs(h[i] - h[i - 1]) + dp[i - 1]);
|
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| #include <bits/stdc++.h>
using namespace std;
int bottomup(vector<int> &h)
{
int n = h.size();
vector<int> dp(n);
dp[0] = 0, dp[1] = abs(h[1] - h[0]);
for (int i = 2; i < n; ++i)
dp[i] = min(abs(h[i] - h[i - 2]) + dp[i - 2],
abs(h[i] - h[i - 1]) + dp[i - 1]);
return dp[n - 1];
}
int main()
{
int n;
cin >> n;
vector<int> h(n);
for (int i = 0; i < n; ++i)
cin >> h[i];
cout << bottomup(h);
return 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| n = int(input())
nums = list(map(int, input().strip().split()))
def bottomUp(nums, n):
dp = [0] * n
dp[0] = 0
dp[1] = abs(nums[0] - nums[1])
for i in range(2, n):
dp[i] = min(abs(nums[i] - nums[i - 1]) + dp[i - 1],
abs(nums[i] - nums[i - 2]) + dp[i - 2])
return dp[n-1]
print(bottomUp(nums, n))
|
Complexity Analysis
- Time complexity: $\boldsymbol{O(n)}$ - We have single for loop that run in total of $n$ times.
- Space complexity: $\boldsymbol{O(n)}$ - We are caching $n$ results in our DP array.