Dynamic Programming in R
R is very vector-based. You’re supposed to formulate your solution in terms of operations across whole vectors. This is great for a lot of problems11 The vector-based nature is actually the reason I wanted to learn apl or j, but never got around to it. Now that I know r is similar, I don’t feel the same need to learn an apl-like language anymore!! But sometimes we want to operate on individual elements of a vector, one at a time, for performance reasons.
Such as, for example, when we want to do dynamic programming.
The Game of Dicey Munch
Figure 1: Attribution: Copyright © Alper Çuğun 2015. Published under CC-BY 2.0.
So imagine you’re on a game show called Dicey Munch. The host has a shuffled deck of cards, where each card either has a picture of a cockroach or a toothpaste tube on it. The game show host will give you two options.
- You can pick a random card from their deck, and if it is a cockroach card, you have to eat a cockroach and you lose a point. If it is a toothpaste card, you get to brush your teeth and you win a point. The deck is then restored and reshuffled, and the game restarts.
- If you don’t want to pick a card, the host offers to throw a dice. If it comes out six, the host will remove a cockroach card from the deck22 Thus improving your chances of gaining points.. If it comes out anything else, the host will remove a toothpaste card from the deck33 Reducing your chances of gaining points.. Then you get to choose between picking a card and throwing a dice again.
You begin with ten points. If you reach zero points you lose and you go home, probably with a bad aftertaste. If you get 20 points, you win and you get a years’ supply of toothpaste.