Skip to content
National Programming Challenge
Back to libraryPart 3 · Graphs and dynamic programming

3.4Dynamic programming I

Before you start

It helps to have read 2.4 Recursion and backtracking and 3.1 Graph search: BFS and DFS. Overall level: Intermediate.

Practice: Dynamic programming I

0 of 4 solved

About these problems

Apply, Connect, Reason and Stretch describe difficulty within this topic, not an official contest rating. Open any problem in any order; reading the chapter first is optional.

  1. 1Step sequencesCount ordered sequences of moves of length 1 or 2 that sum to n. The empty sequence counts once when n=0. Print the count modulo 1000000007.ApplyNot started
  2. 2Fewest coinsYou have unlimited copies of n distinct positive coin denominations. Find the minimum coins needed to sum to x exactly, or -1 if impossible.ConnectNot started
  3. 3Grid route countCount routes from top-left to bottom-right of a grid, moving only one cell right or down. Blocked cells may not be used. Print the count modulo 1000000007.ReasonNot started
  4. 4Separated selectionsChoose any positions of an array, with no two chosen positions adjacent. Maximize their value sum. Choosing no position is allowed.StretchNot started

Read the lesson