[CC150] Chapter 9 Recursion and Dynamic Programming
9.1 A child is running up a staircase with n steps, and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child can run up the stairs.
A simplified version is in leetcode as Climbing Stairs.
9.2 Imagine a robot sitting on the upper left corner of an X by Y grid. The robot can only move in two directions: right and down. How many possible paths are there for the robot to go from (0, 0) to (X, Y)?
FOLLOW UP
Imagine certain spots are "off limits", such that the robot cannot step on them. Design an algorithm to find a path for the robot from the top left to the bottom right.
This problem is in leetcode as Unique Paths and Unique Paths II.
9.3 A magic index in an array A[1... n-1] is defined to be an index such that A[i] = i. Given a sorted array of distinct integers, write a method to find a magic index, if one exists, in array A.
FOLLOW UP
What if the values are not distinct?
9.4 Write a method to return all subsets of a set.
This problem is in leetcode as Subsets and Subsets II.
9.5 Write a method to compute all permutations of a string.
Consider a string as a char array, this problem is equivalent to Permutations.
Related problems: Permutations II, Permutation Sequence, Next Permutation.
9.6 Implement an algorithm to print all valid (i.e., properly opened and closed) combinations of n-pairs of parentheses.
This problem is in leetcode as Generate Parentheses.
Related problems: Longest Valid Parentheses and Valid Parentheses.
9.7 Implement the "paint fill" function that one might see on many image editing programs. That is, given a screen (represented by a two-dimensional array of colors), a point, and a new color, fill in the surrounding area until the color changes from the original color.
This can be easily done by simple recursive BFS.
9.8 Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent), write code to calculate the number of ways of representing n cents.
9.9 Write an algorithm to print all ways of arranging eight queens on an 8x8 chess board so that none of them share the same row, column or diagonal.
This problem is in leetcode as N Queens.
Related problem: N Queens II.
9.10 You have a stack of n boxes, with widths w_i, heights h_i, and depths d_i. The boxes cannot be rotated and can only be stacked on top of one another if each box in the stack is strictly larger than the box above it in width, height, and depth. Implement a method to build the tallest stack possible, where the height of a stack is the sum of the heights of each box.
9.11 Given a boolean expression consisting of the symbols 0, 1, &, |, and ^, and a desired boolean result value. Implement a function to count the number of ways of parenthesizing the expression such that it evaluates to result.
A simplified version is in leetcode as Climbing Stairs.
9.2 Imagine a robot sitting on the upper left corner of an X by Y grid. The robot can only move in two directions: right and down. How many possible paths are there for the robot to go from (0, 0) to (X, Y)?
FOLLOW UP
Imagine certain spots are "off limits", such that the robot cannot step on them. Design an algorithm to find a path for the robot from the top left to the bottom right.
This problem is in leetcode as Unique Paths and Unique Paths II.
9.3 A magic index in an array A[1... n-1] is defined to be an index such that A[i] = i. Given a sorted array of distinct integers, write a method to find a magic index, if one exists, in array A.
FOLLOW UP
What if the values are not distinct?
9.4 Write a method to return all subsets of a set.
This problem is in leetcode as Subsets and Subsets II.
9.5 Write a method to compute all permutations of a string.
Consider a string as a char array, this problem is equivalent to Permutations.
Related problems: Permutations II, Permutation Sequence, Next Permutation.
9.6 Implement an algorithm to print all valid (i.e., properly opened and closed) combinations of n-pairs of parentheses.
This problem is in leetcode as Generate Parentheses.
Related problems: Longest Valid Parentheses and Valid Parentheses.
9.7 Implement the "paint fill" function that one might see on many image editing programs. That is, given a screen (represented by a two-dimensional array of colors), a point, and a new color, fill in the surrounding area until the color changes from the original color.
This can be easily done by simple recursive BFS.
9.8 Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent), write code to calculate the number of ways of representing n cents.
9.9 Write an algorithm to print all ways of arranging eight queens on an 8x8 chess board so that none of them share the same row, column or diagonal.
This problem is in leetcode as N Queens.
Related problem: N Queens II.
9.10 You have a stack of n boxes, with widths w_i, heights h_i, and depths d_i. The boxes cannot be rotated and can only be stacked on top of one another if each box in the stack is strictly larger than the box above it in width, height, and depth. Implement a method to build the tallest stack possible, where the height of a stack is the sum of the heights of each box.
9.11 Given a boolean expression consisting of the symbols 0, 1, &, |, and ^, and a desired boolean result value. Implement a function to count the number of ways of parenthesizing the expression such that it evaluates to result.
Comments
Post a Comment