text: d | C ++ program to find the size of the minimum dominating set of the tree ; Definition of a tree node ; Helper function that allocates a new node ; DP array to precompute and store the results ; minDominatingSettion to return the size of the minimum dominating set of the array ; Base case ; Setting the compulsory value if needed ; Check if the answer is already computed ; If it is compulsory to select the node ; Choose the node and set its children as covered ; If it is covered ; If the current node is neither covered nor needs to be selected compulsorily ; Store the result ; Driver code ; initialising the DP array ; Constructing the tree
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  1005 NEW_LINE struct Node { int data ; Node * left , * right ; } ; Node * newNode ( int data ) { Node * node = new Node ( ) ; node -> data = data ; node -> left = node -> right = NULL ; return node ; } int dp [ N ] [ 5 ] [ 5 ] ; int minDominatingSet ( Node * root , int covered , int compulsory ) { if ( ! root ) return 0 ; if ( ! root -> left and ! root -> right and ! covered ) compulsory = true ; if ( dp [ root -> data ] [ covered ] [ compulsory ] != -1 ) return dp [ root -> data ] [ covered ] [ compulsory ] ; if ( compulsory ) { return dp [ root -> data ] [ covered ] [ compulsory ] = 1 + minDominatingSet ( root -> left , 1 , 0 ) + minDominatingSet ( root -> right , 1 , 0 ) ; } if ( covered ) { return dp [ root -> data ] [ covered ] [ compulsory ] = min ( 1 + minDominatingSet ( root -> left , 1 , 0 ) + minDominatingSet ( root -> right , 1 , 0 ) , minDominatingSet ( root -> left , 0 , 0 ) + minDominatingSet ( root -> right , 0 , 0 ) ) ; } int ans = 1 + minDominatingSet ( root -> left , 1 , 0 ) + minDominatingSet ( root -> right , 1 , 0 ) ; if ( root -> left ) { ans = min ( ans , minDominatingSet ( root -> left , 0 , 1 ) + minDominatingSet ( root -> right , 0 , 0 ) ) ; } if ( root -> right ) { ans = min ( ans , minDominatingSet ( root -> left , 0 , 0 ) + minDominatingSet ( root -> right , 0 , 1 ) ) ; } return dp [ root -> data ] [ covered ] [ compulsory ] = ans ; } signed main ( ) { memset ( dp , -1 , sizeof ( dp ) ) ; Node * root = newNode ( 1 ) ; root -> left = newNode ( 2 ) ; root -> left -> left = newNode ( 3 ) ; root -> left -> right = newNode ( 4 ) ; root -> left -> left -> left = newNode ( 5 ) ; root -> left -> left -> left -> left = newNode ( 6 ) ; root -> left -> left -> left -> right = newNode ( 7 ) ; root -> left -> left -> left -> right -> right = newNode ( 10 ) ; root -> left -> left -> left -> left -> left = newNode ( 8 ) ; root -> left -> left -> left -> left -> right = newNode ( 9 ) ; cout << minDominatingSet ( root , 0 , 0 ) << endl ; return 0 ; }