I am trying to solve the so-called "Hopper tower problem" with a recursive approach. This problem consists of:
- Array given as input. (ex: towers = [2,2,4,0,2]).
- You start at tower[0]
- Maximum distance you can travel corresponds to your current position in the array. Example: if you are at towers[1], you can go to either towers[2] or towers[3], as the height of your tower is 2.
- The function should return false if there is no possible configuration that allows you to reach the end of the array.
This exercise can be found better explained here "https://www.youtube.com/watch?v=kHWy5nEfRIQ". However, I want to practice the recursive/DP approach. My current solution must be close, but I have one problem. My helper function always returns a few falses (from those nodes that could not reach the end of the array). Due to this, my final function always returns false, and I do not know how to solve it despite I have searched for the solutions in other sites. Is it common that these functions return different boolean to be interpreted? Or do I have to avoid it (although I do not know how)?
Thank you
My code is here:
#include <stdio.h>
#include <iostream>
using namespace std;
//Tower = array of towers
//ptr = current position (pointer)
//n = size of array tower
bool helper(int* tower, int ptr, const int n){
if ((ptr + tower[ptr]) >= n) { //Stop condition
return true;
}
else{
if (tower[ptr] != 0){
for (int i = 1; i <= tower[ptr]; i++)
helper(tower, ptr + i, n);
}
}
return false;
}
bool dpTower(int* tower, int const n) {
return helper(tower, 0, n);
}
int main()
{
int tower[] = { 2,2,0,4,2,0 };
int length = sizeof(tower) / sizeof(tower[0]);
bool hoppable = dpTower(tower, length);
if (hoppable == true)
cout << "It is hoppable";
else
cout << "It is not hoppable";
return 0;
}
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…