Of course, I did nothing of the kind, I had already decided that there must be a dynamic programming solution so I went ahead and tried to come up with it myself. It took me quite a while to come up with that definition, but once you have something like that, you can do some research and see if it is a known problem. In this case the activities list is just extraneous information, what we really have is a list of numbers and we need to find a subset of these numbers where the sum of the subset is equal to a particular value. The first part of solving any problem is to really understand what problem you’re trying to solve ( that one sentence really deserves its own article). So, I went for a walk :) and when I came back I settled in to analyse it for real. It sounded easy enough until ****I thought about it and realised it was more complex than it first appeared. We get a list of up to 50 activities and an associated calorie value for each (either positive or negative), we need to find a subset of activities where the sum of all the calorie values is zero. The full description of the problem is on the challenge page, but here is the gist of it. Challenge 3 ( The Dropbox Diet) immediately caught my eye since it looked like one of those problems that should have a dynamic programming solution, so I decided to use it as an opportunity to practice. Apparently, the Dropbox guys have posted up some coding challenges for people who want to apply to work there ( and everyone else, I guess, since it’s on the internet and all :)). I was surfing the web the other day and in the course of my random wanderings I ended up at the Dropbox programming challenges page. Anyway, I don’t want to expound on this, I have something more interesting in mind. The issue with dynamic programming ( besides the totally misleading name), is that it can be very difficult to see how to apply it to a particular problem and even when you do, it is a real pain to get it right. It is an algorithmic technique that the vast majority of developers never master, which is unfortunate since it can help you come up with viable solutions for seemingly intractable problems. Lately I’ve slowly been trying to grok the fullness of dynamic programming.
0 kommentar(er)
