Implementation of House Robber Problem algorithm.
More...
#include <cassert>
#include <climits>
#include <iostream>
#include <vector>
Implementation of House Robber Problem algorithm.
Solution of House robber problem uses a dynamic programming concept that works in \(O(n)\) time and works in \(O(1)\) space.
- Author
- Swastika Gupta
◆ houseRobber()
std::uint32_t dynamic_programming::house_robber::houseRobber |
( |
const std::vector< uint32_t > & | money, |
|
|
const uint32_t & | n ) |
The main function that implements the House Robber algorithm using dynamic programming.
- Parameters
-
money | array containing money in the ith house |
n | size of array |
- Returns
- maximum amount of money that can be robbed
37 {
38 if (n == 0) {
39 return 0;
40 }
41 if (n == 1) {
42 return money[0];
43 }
44 if (n == 2) {
45
47 }
48 uint32_t max_value = 0;
49 uint32_t value1 = money[0];
50 uint32_t value2 =
std::max(money[0], money[1]);
51 for (uint32_t i = 2; i < n; i++) {
52 max_value =
std::max(money[i] + value1, value2);
53 value1 = value2;
54 value2 = max_value;
55 }
56
57 return max_value;
58}
◆ main()
Main function.
- Returns
- 0 on exit
111 {
113 return 0;
114}
static void test()
Self-test implementations.
Definition house_robber.cpp:66
◆ test()
Self-test implementations.
- Returns
- void
66 {
67
68
71 assert(
72 dynamic_programming::house_robber::houseRobber(array1, array1.
size()) ==
73 4);
74
76
77
78
81 assert(
82 dynamic_programming::house_robber::houseRobber(array2, array2.
size()) ==
83 19);
84
86
87
88
91 assert(
92 dynamic_programming::house_robber::houseRobber(array3, array3.
size()) ==
93 0);
95
96
97
100 assert(
101 dynamic_programming::house_robber::houseRobber(array4, array4.
size()) ==
102 12);
103
105}