Stolen Values Problem using Dynamic Programming

This is a C++ Program that Solves Stolen Values Problem using Dynamic Programming technique.

Problem Description

There are n houses built in a line, each of which contain some value in it. A thief is going to steal in these houses. But he cannot steal in two adjacent houses. What is maximum value he can steal?

Problem Solution

Maximum stolen value from first i houses of the line can be either the maximum stolen value from first i-1 houses of the line or maximum stolen value from i-2 houses of the line plus value in ith house. So, we will choose maximum of these. We will calculate the values in bottom up manner.

Expected Input and Output

Case-1:

 
number of houses=7
values[]=9, 3, 5, 8, 2, 4, 7
maximum stolen value=24 by stealing from first, fourth and seventh house

Program/Source Code

Here is source code of the C++ Program to Solve Stolen Values Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include<iostream>
```
```
 
```
```
using namespace std;
```
```
 
```
```
int maxStolen(int n, int values[])
```
```
{
```
```
    //array to store results
```
```
    int dp[n+1];
```
```
 
```

    //dp[i]=maximum stolen value from first i houses

```
 
```
```
    dp[0]=0;
```
```
    dp[1]=values[1];
```
```
 
```
```
    for(int i=2;i<=n;i++)
```
```
    {
```

        //maximum stolen value from first i houses of the line can be

        //either the maximum stolen value from first i-1 houses of the line

        //or maximum stolen value from i-2 houses of the line plus value in ith house

        //so, we will choose maximum of these

        dp[i]=max(dp[i-1],dp[i-2]+values[i]);

```
    }
```
```
 
```
```
    return dp[n];
```
```
}
```
```
 
```
```
 
```
```
int main()
```
```
{
```
```
    int n;
```

    cout<<"Enter the number of houses"<<endl;

```
    cin>>n;
```
```
 
```
```
    int values[n+1];
```

    cout<<"Enter the values in the houses"<<endl;

```
    for(int i=1;i<=n;i++)
```
```
        cin>>values[i];
```
```
 
```

    cout<<"Maximum stolen value is "<<endl;

```
    cout<<maxStolen(n, values);
```
```
 
```
```
    cout<<endl;
```
```
    return 0;
```
```
}
```

Program Explanation

In the main function, we ask the user to input the value of number of houses and values in each house to be stolen. We pass these values to the function maxStolen as parameters. This function will calculate the expected result and return it. The returned value will be displayed.

Runtime Test Cases

 
Case-1:
$ g++ stolen_values.cpp
$ ./a.out
Enter the number of houses
7
Enter the values in the houses
9 3 5 8 2 4 7
Maximum stolen value is 
24

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

If you find any mistake above, kindly email to [email protected]

« Prev - Longest Substring without Duplication – Dynamic Programming Solutions

» Next - Dice Throw Problem – Dynamic Programming Solutions

Related Posts:

Recommended Articles: