Note: This problem is part of the Atcoder Educational Dp Contest
Problem Link
Brute-Force/Recursive Approach
Building from the logic of Frog 1, we know that if a frog can jump k stones ahead from a stone i, this also implies that a frog can only reach stone i by jumping from the previous k stones.
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
| #include <bits/stdc++.h>
using namespace std;
int recursive(vector<int> &h, int k, int i)
{
if (i == 0)
return 0;
int res = INT_MAX;
for (int j = max(0, i - k); j < i; ++j)
res = min(res, abs(h[i] - h[j]) + recursive(h, k, j));
return res;
}
int main()
{
int n, k;
cin >> n >> k;
vector<int> h(n);
for (int i = 0; i < n; ++i)
cin >> h[i];
cout << recursive(h, k, n-1);
return 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| n, k = input().split()
n = int(n)
k = int(k)
h = list(map(int, input().strip().split()))
def recursive(h, k, i):
if i == 0:
return 0
res = math.inf
for j in range (max(0, i - k), i):
res = min(res, abs(h[i] - h[j]) + recursive(h, k, j))
return res
print(recursive(h, k, n-1))
|
Complexity Analysis
- Time complexity: $\boldsymbol{O(n^k)}$ - Size of recursion tree will be $n^k$
- 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
28
29
| #include <bits/stdc++.h>
using namespace std;
int topdown(vector<int> &h, int k, int i)
{
static vector<int> dp(h.size(), -1);
if (dp[i] != -1)
return dp[i];
if (i == 0)
return dp[i] = 0;
int res = INT_MAX;
for (int j = max(0, i - k); j < i; ++j)
res = min(res, abs(h[i] - h[j]) + topdown(h, k, j));
return dp[i] = res;
}
int main()
{
int n, k;
cin >> n >> k;
vector<int> h(n);
for (int i = 0; i < n; ++i)
cin >> h[i];
cout << topdown(h, k, 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, k = input().split()
n = int(n)
k = int(k)
h = list(map(int, input().strip().split()))
dp = [-1 for x in range(0, n)]
def topdown(h, k, i):
if dp[i] != -1:
return dp[i]
if i == 0:
dp[i] = 0
return dp[i]
res = math.inf
for j in range(max(0, i-k), i):
res = min(res, abs(h[i]-h[j]) + topdown(h, k, j))
dp[i] = res
return dp[i]
print(topdown(h, k, n-1))
|
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
| Base Case:
if (i == 0)
return dp[i] = 0;
Recurrence Relation:
dp[i] = max(dp[i], abs(h[i] - h[j]) + dp[j]) -> for all j in range [i-k, i)
|
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
28
29
| #include <bits/stdc++.h>
using namespace std;
int bottomup(vector<int> &h, int k)
{
int n = h.size();
vector<int> dp(n, INT_MAX);
dp[0] = 0;
for (int i = 1; i < n; ++i)
{
for(int j = max(0, i - k); j < i; ++j)
dp[i] = min(dp[i], abs(h[i] - h[j]) + dp[j]);
}
return dp[n - 1];
}
int main()
{
int n, k;
cin >> n >> k;
vector<int> h(n);
for (int i = 0; i < n; ++i)
cin >> h[i];
cout << bottomup(h, k);
return 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| n, k = input().split()
n = int(n)
k = int(k)
h = list(map(int, input().strip().split()))
def bottomup(h, k):
n = len(h)
dp = [math.inf for x in range(0, n)]
dp[0] = 0
for i in range(1, n):
for j in range(max(0, i - k), i):
dp[i] = min(dp[i], abs(h[i] - h[j]) + dp[j])
return dp[n -1]
print(bottomup(h, k))
|
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.