CSES :: Dynamic Programming :: Removing Digits

Problem : Please find the problem here.

Explanation : Zero ways to get to 0, 1 way to get to 0 from any number 1-9...
Recursively find minimum number of ways a number can be reduce to zero, ignore the condition when one of the digit is zero (that will never reduce the number ).

Code : Used Dynamic Programming.

#include <bits/stdc++.h>

using namespace std;

vector<int> getDigits(int n) {
    vector<int> digits;
    while (n) {
        digits.emplace_back(n%10);
        n /= 10;
    }

    return digits;
}

int calculate(int n) {
    vector<int> DP(n+1, INT_MAX);
    DP[0] = 0;

    for (int i = 1; i <= n; i++) {
        auto digits = getDigits(i);
        for (int d : digits) {
            if (d != 0) {
              DP[i] = min(DP[i], 1 + DP[i-d]);
            }
        }
    }

    return DP[n];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n; cin >> n;

    cout <<calculate(n) << '\n';

    return 0;
}

CSES :: Dynamic Programming :: Grid Paths

Problem : Please find the problem here.

Explanation : Solve the subproblem of finding the number of ways we can get (1,1) from position (n, m) recursively. Ignore all paths leading to restricted blocks. Memoize the solution to ensure a substrcture not processed not more than once.

Code : Used Dynamic Programming.

#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9+7;

// DP : Iteration with Memo
int countGridPathIterDP(int n, int m, vector<string> &grid) {

    vector<vector<int>> DP(n, vector<int> (m, 0));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
           if (i == 0 && j == 0) {
               DP[i][j] = (grid[i][j] == '*'?0:1);
           }
           else {
               if (i == 0) {
                   DP[i][j] = (grid[i][j] == '*'?0:DP[i][j-1]);
               } else if (j == 0) {
                   DP[i][j] = (grid[i][j] == '*'?0:DP[i-1][j]);
               } else {
                   DP[i][j] = (grid[i][j] == '*'?0:(DP[i-1][j]%mod + DP[i][j-1]%mod)%mod);
               }
           }

        }
    }

    return DP[n-1][m-1];
}

// DP : Recursion with Memo

int countGridPathRecurDP(int n, int m, vector<string> &grid, vector<vector<int>> &DP) {

    if (DP[n][m] != -1)  return DP[n][m];

    if (n == 0 && m == 0 && grid[n][m] != '*') return 1;
     if ((n < 0 || m < 0) || grid[n][m] == '*') return 0;

    DP[n-1][m] = countGridPathRecurDP(n-1, m, grid, DP)%mod;
    DP[n][m-1] = countGridPathRecurDP(n, m-1, grid, DP)%mod;
    DP[n][m] = (DP[n-1][m] + DP[n][m-1])%mod;

    return DP[n][m];
}

int countGridPathRecurDP(int n, int m, vector<string> &grid) {
    vector<vector<int>> DP(n, vector<int> (m, -1));
    return countGridPathRecurDP(n, n, grid, DP);
}

// Plain Recursion
int countGridPathRecur(int n, int m, vector<string> &grid) {
    if (n == 0 && m == 0 && grid[n][m] != '*') return 1;
    if ((n < 0 || m < 0) || grid[n][m] == '*') return 0;

    return (countGridPathRecur(n-1, m, grid)%mod + countGridPathRecur(n, m-1, grid)%mod)%mod;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n; cin >> n;
    vector<string> grid(n+1);
    vector<vector<int>> DP(n+1, vector<int> (n+1, 0));

    for (int i = 0; i < n; i++) {
        cin >> grid[i];
    }
    cout << countGridPathIterDP(n, n, grid);
    return 0;
}

CSES :: Dynamic Programming :: Minimizing Coins

Problem : Please find the problem here.

Explanation : Count number of ways a target sum can be acheived by selecting minimum of the given coins.

Code : Used Dynamic Programming.

#include <bits/stdc++.h>

using namespace std;

const int mxN = 1e9;

int countMinCoins(int sum, vector<int> &coins, vector<int> &DP) {
    int n = coins.size();
    DP[0] = 0;
    for (int i = 1; i <= sum; i++) {
        for (int j = 0; j < n; j++) {
            if (coins[j] <= i) {
                DP[i] = min(DP[i], DP[i - coins[j]] + 1);
            }
        }
    }

    return (DP[sum] == mxN?-1:DP[sum]);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, x;
    cin >> n >> x;
    vector<int> coins(n), DP(x+1, mxN);

    for (int i = 0; i < n; i++) {
        cin >> coins[i];
    }

    cout << countMinCoins(x, coins, DP);
    return 0;
}

CSES :: Dynamic Programming :: Coin Combinations I

Problem : Please find the problem here.

Explanation : For a given target, recursively find the number of ways it can be get by choosing any of the given coins.

Code : Used dynamic programming.

#include <bits/stdc++.h>
using namespace std;

const int mxN = 1e6;
const int mod = 1e9+7;

void calculateDiceCombinations(int n, vector<int>& dp) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= min(i, 6); j++) {
            dp[i] = (dp[i] + dp[i-j]) % mod ;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n; cin >> n;
    vector<int> dp(mxN, 0);

    dp[0] = 1;
    calculateDiceCombinations(n, dp);

    cout << dp[n] << '\n';

    return 0;
}

CSES :: Dynamic Programming :: Dice Combinations

Problem : Please find the problem here.

Explanation : The number of ways to get a certain value is dependent on the outcomes of previous die throws.

Code : Iterating over values from 1 to n and for each value And accumulating the ways to reach the current value by summing all the possibilities based on the outcomes of previous throws.

Time Complexity : O(n).

#include <bits/stdc++.h>
using namespace std;

const int mxN = 1e6;
const int mod = 1e9+7;

void calculateDiceCombinations(int n, vector<int>& dp) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= min(i, 6); j++) {
            dp[i] = (dp[i] + dp[i-j]) % mod ;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n; cin >> n;
    vector<int> dp(mxN, 0);

    dp[0] = 1;
    calculateDiceCombinations(n, dp);

    cout << dp[n] << '\n';

    return 0;
}

Subset Sum Problem

Problem Statement:   Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.

1. For every element In the array, we have a choice of whether to select this item or not.
2. If the value of the element is strictly greater than the Sum, the element cannot be taken. But, if the value of the element is not greater than Sum, then we have two choices. we either choose the element or we don't choose the element. 
3. If we choose the element the Sum should be decrease by the value of the element. If we dont choose the element the Sum left unchanged. 
4. After this the nth array element is now processed. we move to next array element which    (n-1) the element with new Sum value. so now we have the new sub-porblem.
5. we do this recursively for every array element solving the subproblems  eventually  the      original problem is solved.


/*
Let our arr[n] be the given array and  DP[n][S], a boolean value, represent sif there exists a subset with sum S and n elements;
then, 
if( arr[n] <= S) --> DP[n][S] = DP[n-1][S-arr[n]] or DP[n-1][S];
else --> DP[n][S] = dp[n-1][S];

*/

In recursive (TOP-DOWN) approach our task is to divide the given problem in the further subproblems.


// Recursive Method.

//Iterative Method

Dynamic Programming

Dynamic Programming is a problem solving technique that solves a problem by dividing it into its subproblems. When the subproblems are similar that is they share the same property as the original problem and also they are dependent. It is normally used for optimizing a specific problem and follows the principle of optimality which states that for an optimal sequence of decisions, each sub-sequence must also be optimal.

List of possible parent DP problems with the possible least number of their variations(mentioned in square brackets). (source: google)

1. 0-1 Knapsack[6]
2. Unbounded Knapsack[5]
3. Fibonacci[7]
4. Longest Common Subsequence[15]
5. Longest Increasing Subsequenc[10]
6. Kadane's Algorith[6]
7. Matrix Chain Multiplication[7]
8. DP on Trees[7]
9. DP on Grid[14]
10. Others(less common)[5]

so there are atleast 83 types of DP problems. There are possibly more which i dont know at this point.
Anyways, I will be studying and blogging about each of these porblems and their varations..

Happy Coding!

Knapsack Problems

Nowdays I'm studying recursion, dynamic programming, solved some problems on it. There's this particular problem I was studying on, its called the knapsack problem.

I had so much trouble solving some knapsack problems, some were easy, some were clear to me but i couldnt solve them, later found that those problems were not of the same type even though they sound similar and i was constantly trying to tackle them with the same method.. Failed doing so. So I thought there must be some general types of knapsack problems. I did some googling and found that there are atleast six types of knapsack problems.

Knapsack problem is a name to a family optimization problems that have the following general theme: You are given a knapsack with a maximum weight/ capacity, and you have to select a subset of some given items such that a profit sum is maximium, without exceeding the capacity of the knapsack.

Further learnt that knapsack problem is a NP-hard problem. NP is a complexity class of computational problems and NP hard is the hardest among all the NP problems. Sounds scary right?, I think that  explains why most DP problems have so small constraints. The easiest method to solve this problems is Dynamic Programming , which solves these problems in pseudo polynomial time.


Types of Knapsack problems;

1. 0/1 knapsack problem : most basic type, given a knapsack with a maximum weight, and you have to select a subset of some given items such that a profit sum is maximized without exceeding the capacity of the knapsack.
2. Number partitioning : Partition a set S containing N integers, into two sets S1 and S2, so that |sum(L1) - sum(L2)| is minimized. This problem is perhaps even more general than the 0/1 knapsack problem and is one of the six basic NP-hard problems.
3. Bounded Knapsack : Instead of N items, you are given M types of items, each type having a bounded quantity.
4. Unbounded Knapsack : You have an unbounded quantity of each item type, instead of a bounded quantity.
5. Multiple Knapsack problem: same as the 0/1 knapsack problem but you are given multiple knapsacks of different sizes. The capacity constraint must be met for all of the knapsacks.
6. Box-packing problem : Also called as The Bin-packing problem. You have some number of equally sized bins. You need to pack the items into bins so that the number of bins used is as small as possible.

Each of this problem have different variations too. For example the 0/1 knapsack problem covers the following problems:

(i) Subset sum problem
(ii) Equal sum partion
(iii) Count of subset
(iv) Minimum subset sum
(v) Target sum

and lot more...


I understand knapsack problem much better now. And I'm confident and excited to solve newer variations of Knapsack problem or atleast similar problems just for fun. Will be posting about the problems with solutions.