The in-house solution from your cheap hosting provider is gonna be expensive... you have to look elsewhere.
When you get cheap hosting, all the other services around tend to be more expensive... just to balance the price out. Or they might be some unnecessary restrictions. But there is a way, you can always go with an external provider.
Although, there are many options out there, I think AWS S3 is quite cheap as a backup solution for your VPS. And one thing you do need from a backup is reliability, which there is no doubt if AWS has it.
While this question might be unnecessary, the backup is definitely not. Anyway, there is no magic behind backup, it is a plain old copy of data.
And AWS S3 is just a storage for data. The good thing is... you pay only for what you use.
In the case of backup, the majority of the time (maybe forever if you are lucky) you will only write data and keep them at rest. You also need your data to be secure, so nobody can access them without permission. S3 has all of that... your data can be encrypted and you can manage permissions for accessing it.
The pricing of AWS at the time I am writing this is $0.0135 per GB / month for Infrequent Access storage class. You can even push the price as low as $0.0045 per GB / month if you go with Glacier, but there are some nasty limitations I don't want to get into right now.
You pay $0.01 for every 1,000 write requests you initiate... so if you are not planning to backup your data every second, you should be fine.
Then you also pay a small fee for the read requests and data transfer from S3. However, this should be only in the case of recovery, thus basically for free.
It also worth checking AWS Free Tier.
Let's consider you do a daily backup of 10GB of data. You will pay around $0.1 per month (cost of storage + write requests).
I used AWS Pricing Calculator to do the heavy math for me.
Unlike a ready-made solution from the hosting provider, you need some code to do the backup.
If you are using Docker, you can check my backup solutions below... if you are not, you can still check them and change them accordingly.