Line: 1 to 1 | |||||||||
---|---|---|---|---|---|---|---|---|---|

## LeetCode Exercise 8## Dynamic Programming## | |||||||||

Changed: | |||||||||

< < |
| ||||||||

> > |
| ||||||||

## Due: April 12, 11:55 pm## 368. Largest Divisible SubsetGiven a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0. If there are multiple solutions, return any subset is fine. ## Example 1: | |||||||||

Added: | |||||||||

> > | |||||||||

nums: [1,2,3] Result: [1,2] (of course, [1,3] will also be ok) ## Example 2: | |||||||||

Added: | |||||||||

> > | |||||||||

nums: [1,2,4,8] Result: [1,2,4,8]
You are to find a ## Hints:- Can you think of a bottom-up approach? How is the larger problem a made up of sub-problems?
- Review the solution in class of Weighted Interval Scheduling. Consider the methods and data structures of that.
- DP usually depends on the ordering of objects. How might ordering here be useful?
- How is an optimal solution for a given size problem useful in constructing a solution for a larger problem.
- For a given problem size of
*n*, can you first solve all of the problems for 0<*i*<=*n*-1 and keep track of those solutions with some sort of a data structure? - If you have solved (and have available) the solutions for all smaller problems, how can you select and use the smaller solutions to create a solution for n?
| |||||||||

Added: | |||||||||

> > | |||||||||

Turn in: - Source code for your solution
- Samples runs showing the operation with input and outputs.
- An explaination of how this problem includes the concept of an optimal substructure.
- A complete runtime asymptotic analysis.
| |||||||||

Added: | |||||||||

> > | |||||||||

Be prepared to discuss you solutions in class. \ No newline at end of file |

View topic | History: r4 < r3 < r2 < r1 | More topic actions...

Copyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.

Ideas, requests, problems regarding TWiki? Send feedback

Ideas, requests, problems regarding TWiki? Send feedback