Open In App

Optimal Substructure Property in Dynamic Programming | DP-2

Last Updated : 27 Mar, 2023
Summarize
Comments
Improve
Suggest changes
Like Article
Like
Save
Share
Report
News Follow
 

As we discussed in Set 1, the following are the two main properties of a problem that suggest that the given problem can be solved using Dynamic programming
1) Overlapping Subproblems 
2) Optimal Substructure 
We have already discussed the Overlapping Subproblem property in Set 1. Let us discuss the Optimal Substructure property here. 

In Dynamic  programming, the ideal base property alludes to the way that an ideal answer for an issue can be built from ideal answers for subproblems. This property is utilized to plan dynamic programming calculations that tackle streamlining issues by separating them into more modest subproblems and afterward consolidating the answers for those subproblems to get an answer for the first issue.
For instance, think about the issue of tracking down the most brief way between two focuses in a diagram. 

On the off chance that we apply dynamic programming to this issue, we can characterize the subproblems as the briefest ways between halfway focuses on the chart, and afterward utilize the answers for those subproblems to build an answer for the first issue.
To show this thought all the more officially, we should assume we disapprove of an ideal arrangement S* and a bunch of subproblems S1, S2, …, Sn. On the off chance that the ideal answer for the issue can be developed from the ideal answers for the subproblems, then the issue displays the ideal base property.
2) Optimal Substructure:

A given problem is said to have Optimal Substructure Property if the optimal solution of the given problem can be obtained by using the optimal solution to its subproblems instead of trying every possible way to solve the subproblems. 
Example: 

The Shortest Path problem has the following optimal substructure property: 

If node x lies in the shortest path from a source node U to destination node V then the shortest path from U to V is a combination of the shortest path from U to X and the shortest path from X to V. The standard All Pair Shortest Path algorithm like Floyd–Warshall and Single Source Shortest path algorithm for negative weight edges like Bellman–Ford are typical examples of Dynamic Programming
On the other hand, the Longest Path problem doesn’t have the Optimal Substructure property. Here by Longest Path, we mean the longest simple path (path without cycle) between two nodes. Consider the following unweighted graph given in the CLRS book. There are two longest paths from q to t: q?r?t and q?s?t. Unlike shortest paths, these longest paths do not have the optimal substructure property. For example, The longest path q?r?t is not a combination of the longest path from q to r and the longest path from r to t, because the longest path from q to r is q?s?t?r and the longest path from r to t is r?q?s?t. 
 

Some Standard problems having optimal substructure are:

S. No.

Article 

Practice Problem

1

Longest Common Subsequence 

solve

2

Count ways to reach the n’th stair 

solve

3

Coin Change 

solve

4

Edit Distance | DP-5 – GeeksforGeeks

solve

5

Cutting a Rod

solve

6

Program for Fibonacci numbers – GeeksforGeeks

solve

The above problems can be solved optimally using Dynamic programming as each of these problems have an optimal substructure, On the other hand, there are some problems that need to be solved by trying all possible solutions one such problem is Rat in a Maze problem. In these types of problems, the optimal solution for subproblems may not surely give the solution to the entire problem. In Rat in a Maze problem, all paths need to be explored to find out the final path from the source that leads to the destination. Thus in these problems, Recursion and Backtracking are the way to go.

Pseudo code: 

for x in V:
 for y in V:
   dp[x][y] = INF

dp[u][u] = 0

for x in V:
 for y in V:
   for z in V:
     if (x, y) is an edge in E:
       dp[x][y] = min(dp[x][y], dp[x][z] + dp[z][y])

return dp[u][v]
 

C++




#include <iostream>
#include <algorithm>
#include <limits>
 
using namespace std;
 
const int N = 100010;
 
// The number of vertices in the graph
int n;
 
// The adjacency matrix representation of the graph
int adj[N][N];
 
// The array for storing the shortest distances between the vertices
int dist[N][N];
 
void floyd() {
  // Initialize the distances with the weights of the edges
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      dist[i][j] = adj[i][j];
    }
  }
 
  // Solve the subproblems using the optimal substructure property
  for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        // Relax the edge (i, j) using the vertex k as the intermediate vertex
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
      }
    }
  }
}
 
int main() {
  // Read the input
  cin >> n;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> adj[i][j];
      if (adj[i][j] == 0) {
        // There is no edge between the vertices
        adj[i][j] = numeric_limits<int>::max();
      }
    }
  }
 
  // Solve the shortest path problem
  floyd();
 
  // Print the shortest distances between the vertices
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cout << i << " " << j << " " << dist[i][j] << endl;
    }
  }
 
  return 0;
}


Java




import java.util.Arrays;
import java.util.List;
import java.util.Map;
 
class ShortestPath {
  static final int INF = Integer.MAX_VALUE;
 
  static int shortestPath(int[][] graph, int u, int v) {
    int n = graph.length;
    int[][] dp = new int[n][n];
    for (int[] row : dp) {
      Arrays.fill(row, INF);
    }
 
    dp[u][u] = 0;
 
    for (int x = 0; x < n; x++) {
      for (int y = 0; y < n; y++) {
        for (int z = 0; z < n; z++) {
          if (graph[x][y] != INF) {
            dp[x][y] = Math.min(dp[x][y], dp[x][z] + dp[z][y]);
          }
        }
      }
    }
 
    return dp[u][v];
  }
 
  public static void main(String[] args) {
    // Example graph
    int[][] graph = {
      {0,   5,   INF, 10},
      {INF, 0,   3,   INF},
      {INF, INF, 0,   1},
      {INF, INF, INF, 0}
    };
 
    int shortestPath = shortestPath(graph, 0, 3);
    System.out.println("Shortest path from 0 to 3: " + shortestPath);
  }
}


Python3




# The number of vertices in the graph
N = 100010
 
# The adjacency matrix representation of the graph
adj = [[0 for j in range(N)] for i in range(N)]
 
# The array for storing the shortest distances between the vertices
dist = [[0 for j in range(N)] for i in range(N)]
 
def floyd():
    global N, adj, dist
    # Initialize the distances with the weights of the edges
    for i in range(N):
        for j in range(N):
            dist[i][j] = adj[i][j]
 
    # Solve the subproblems using the optimal substructure property
    for k in range(N):
        for i in range(N):
            for j in range(N):
                # Relax the edge (i, j) using the vertex k as the intermediate vertex
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
 
if __name__ == "__main__":
    # Read the input
    n = int(input())
    for i in range(n):
        line = input().strip().split()
        for j in range(n):
            adj[i][j] = int(line[j])
            if adj[i][j] == 0:
                # There is no edge between the vertices
                adj[i][j] = sys.maxsize
 
    # Solve the shortest path problem
    floyd()
 
    # Print the shortest distances between the vertices
    for i in range(n):
        for j in range(n):
            print(i, j, dist[i][j])


C#




using System;
using System.Collections.Generic;
 
class ShortestPath {
    static readonly int INF = int.MaxValue;
 
    static int shortestPath(int[,] graph, int u, int v) {
        int n = graph.GetLength(0);
        int[,] dp = new int[n, n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i, j] = INF;
            }
        }
 
        dp[u, u] = 0;
 
        for (int x = 0; x < n; x++) {
            for (int y = 0; y < n; y++) {
                for (int z = 0; z < n; z++) {
                    if (graph[x, y] != INF) {
                        dp[x, y] = Math.Min(dp[x, y], dp[x, z] + dp[z, y]);
                    }
                }
            }
        }
 
        return dp[u, v];
    }
 
    public static void Main(string[] args) {
        // Example graph
        int[,] graph = {
            {0,   5,   INF, 10},
            {INF, 0,   3,   INF},
            {INF, INF, 0,   1},
            {INF, INF, INF, 0}
        };
 
        int shortestpath = shortestPath(graph, 0, 3);
        Console.WriteLine("Shortest path from 0 to 3: " + shortestpath);
    }
}


Javascript




// Initialize the required libraries
// and declare the class 'ShortestPath'
const Arrays = require('java.util.Arrays');
const List = require('java.util.List');
const Map = require('java.util.Map');
 
class ShortestPath {
// Declare the constant value for maximum integer
static const INF = Number.MAX_VALUE;
 
// Declare the static method for finding the shortest path
static shortestPath(graph, u, v) {
// Get the number of vertices in the graph
const n = graph.length;
// Initialize the 2D array for dynamic programming
const dp = new Array(n).fill().map(() => new Array(n).fill(INF));
 
// Fill the diagonal elements with 0
dp[u][u] = 0;
 
// Iterate through all the vertices
for (let x = 0; x < n; x++) {
  for (let y = 0; y < n; y++) {
    for (let z = 0; z < n; z++) {
      // Check if there is an edge between the vertices
      if (graph[x][y] !== INF) {
        dp[x][y] = Math.min(dp[x][y], dp[x][z] + dp[z][y]);
      }
    }
  }
}
 
// Return the shortest path from u to v
return dp[u][v];
}
 
// Declare the main function for testing
static main(args) {
// Declare the example graph
const graph = [
[0, 5, INF, 10],
[INF, 0, 3, INF],
[INF, INF, 0, 1],
[INF, INF, INF, 0]
];
// Find the shortest path from vertex 0 to vertex 3
const shortestPath = ShortestPath.shortestPath(graph, 0, 3);
 
// Print the result
console.log(`Shortest path from 0 to 3: ${shortestPath}`);
}
}
 
// Call the main function for testing
ShortestPath.main();


We will be covering some example problems in future posts on Dynamic Programming
 
References: 
http://en.wikipedia.org/wiki/Optimal_substructure 
CLRS book
 



Previous Article
Next Article

Similar Reads

Optimal Strategy for the Divisor game using Dynamic Programming
Given an integer N and two players, A and B are playing a game. On each player’s turn, that player makes a move by subtracting a divisor of current N (which is less than N) from current N, thus forming a new N for the next turn. The player who does not have any divisor left to subtract loses the game. The task is to tell which player wins the game
9 min read
Dynamic Programming in Game Theory for Competitive Programming
In the fast-paced world of competitive programming, mastering dynamic programming in game theory is the key to solving complex strategic challenges. This article explores how dynamic programming in game theory can enhance your problem-solving skills and strategic insights, giving you a competitive edge. Whether you're a seasoned coder or a newcomer
15+ min read
Overlapping Subproblems Property in Dynamic Programming | DP-1
Dynamic Programming is an algorithmic paradigm that solves a given complex problem by breaking it into subproblems using recursion and storing the results of subproblems to avoid computing the same results again. Following are the two main properties of a problem that suggests that the given problem can be solved using Dynamic programming. Overlapp
10 min read
Secretary Problem (A Optimal Stopping Problem)
The Secretary Problem also known as marriage problem, the sultan's dowry problem, and the best choice problem is an example of Optimal Stopping Problem. This problem can be stated in the following form: Imagine an administrator who wants to hire the best secretary out of n rankable applicants for a position. The applicants are interviewed one by on
12 min read
Optimal Page Replacement Algorithm
Prerequisite: Page Replacement Algorithms In operating systems, whenever a new page is referred and not present in memory, page fault occurs and Operating System replaces one of the existing pages with newly needed page. Different page replacement algorithms suggest different ways to decide which page to replace. The target for all algorithms is to
15+ min read
Optimal partition of an array into four parts
Given an array of n non-negative integers. Choose three indices i.e. (0 <= index_1 <= index_ 2<= index_3 <= n) from the array to make four subsets such that the term sum(0, index_1) - sum(index_1, index_2) + sum(index_2, index_3) - sum(index_3, n) is maximum possible. Here, two indices say l and r means, the sum(l, r) will be the sum of
9 min read
Optimal sequence for AVL tree insertion (without any rotations)
Given an array of integers, the task is to find the sequence in which these integers should be added to an AVL tree such that no rotations are required to balance the tree. Examples : Input : array = {1, 2, 3} Output : 2 1 3 Input : array = {2, 4, 1, 3, 5, 6, 7} Output : 4 2 6 1 3 5 7 Approach : Sort the given array of integers.Create the AVL tree
8 min read
Optimal File Merge Patterns
Given n number of sorted files, the task is to find the minimum computations done to reach the Optimal Merge Pattern. When two or more sorted files are to be merged altogether to form a single file, the minimum computations are done to reach this file are known as Optimal Merge Pattern. If more than 2 files need to be merged then it can be done in
9 min read
Optimal Strategy for a Game | Set 2
Problem statement: Consider a row of n coins of values v1 . . . vn, where n is even. We play a game against an opponent by alternating turns. In each turn, a player selects either the first or last coin from the row, removes it from the row permanently, and receives the value of the coin. Determine the maximum possible amount of money we can defini
15+ min read
Find optimal weights which can be used to weigh all the weights in the range [1, X]
Given an integer X, the task is to find an optimal set of weights {w1, w2, w3, ..., wn} such that we can weigh/determine all the weights from 1 to X using a two-sided weighing balance pan. Note that all the weights must be unique and n should be as minimum as possible.Examples: Input: X = 7 Output: 1 3 9 WeightsLeft SideRight Side11122 + 13333441 +
4 min read
Optimal Strategy for a Game | Set 3
Consider a row of n coins of values v1 . . . vn, where n is even. We play a game against an opponent by alternating turns. In each turn, a player selects either the first or last coin from the row, removes it from the row permanently, and receives the value of the coin. Determine the maximum possible amount of money we can definitely win if we move
15+ min read
Optimal Array
Given a sorted array A[] of length N. For each i(0 ≤ i ≤ n-1), you have to make all the elements of the array from index 0 to i equal, using the minimum number of operations. In one operation you either increase or decrease the array element by 1. the task is to return a list that contains the minimum number of operations for each i, to accomplish
7 min read
The Optimal Selection in an Array
There is an array given, the task is to select all of these integers in any order. For selecting every integer you get some points, and you need to maximize those points. For every integer you select, you get points equal to the value of the selected integer * the number of integers selected before the current integer, the task is to find the maxim
4 min read
Find Next Optimal Range in Array
Given an array ranges[][] of size N x 2, where for every i, range[i][0] is the start and range[i][1] is the end of the range. For every range, find the index of the Next Optimal Range. For a range i which ends at a point X, all the ranges that have their starting points >= X will be the Next Optimal Range. In the case of multiple Next Optimal Ra
7 min read
Optimal Path in Matrix
Given a matrix grid[][] of size M * N, where grid[i][j] represents the value of the cell at position (i, j), the task is to determine an optimal path from the top-left corner to the bottom-right corner while minimizing the maximum value of |grid[i1][j1] - grid[i2][j2]| for adjacent cells along the path. Example: Input: {{2,2,2}, {2,8,4}, {1,2,2}};O
12 min read
Optimal Binary Search Tree | DP-24
An Optimal Binary Search Tree (OBST), also known as a Weighted Binary Search Tree, is a binary search tree that minimizes the expected search cost. In a binary search tree, the search cost is the number of comparisons required to search for a given key. In an OBST, each node is assigned a weight that represents the probability of the key being sear
15+ min read
Optimal read list for given number of days
A person is determined to finish the book in 'k' days but he never wants to stop a chapter in between. Find the optimal assignment of chapters, such that the person doesn't read too many extra/less pages overall. Example: Input: Number of Days to Finish book = 2 Number of pages in chapters = {10, 5, 5} Output: Day 1: Chapter 1 Day 2: Chapters 2 and
15+ min read
Finding optimal move in Tic-Tac-Toe using Minimax Algorithm in Game Theory
Prerequisites: Minimax Algorithm in Game Theory, Evaluation Function in Game TheoryLet us combine what we have learnt so far about minimax and evaluation function to write a proper Tic-Tac-Toe AI (Artificial Intelligence) that plays a perfect game. This AI will consider all possible scenarios and makes the most optimal move. Finding the Best Move :
15+ min read
Optimal Placement of People in Circular Locations
Given two integers N and K. Consider N locations which are circularly connected (Formally, after the Nth location the next location is 1st location). Then your task is to place K people into N circular locations such that the maximum distance between two consecutive persons is as less as possible. Also, output the minimum number of consecutive pair
6 min read
Optimal Strategy for a Game | DP-31
Consider a row of N coins of values V1 . . . Vn, where N is even. We play a game against an opponent by alternating turns. In each turn, a player selects either the first or last coin from the row, removes it from the row permanently, and receives the value of the coin. Determine the maximum possible amount of money we can definitely win if we move
15+ min read
Optimal cell in matrix to collect maximum coins
Given an M * N matrix matrix[][], where each cell is either an obstacle '#', a coin 'C', or empty '0', the task is to choose one empty cell optimally to maximize the coins collected. You can collect coins from the same row and column where you stand until there are no obstacles. Note: We can only start from the empty cells, that is where matrix[i][
14 min read
Optimal Construction of Roads
Given a connected graph with N nodes and N-1 bidirectional edges given by a 2D array edges[][], such that edges[i] = {u, v, w} states that there is a bidirectional edge between node u and node v with a weight of w. The task is to answer Q queries such that for each query, query[i] = {u, v, w} print "1" if adding a new edge between node u and node v
14 min read
Optimal strategy for a Game with modifications
It is strongly recommended to first refer Optimal Strategy for a Game problem as a prerequisite. Let us now talk about a variation problem. Consider a row of n coins of values v1 . . . vn, where n is even. We play a game against an opponent by alternating turns. In each turn, a player performs the following operation K times.The player selects eith
10 min read
Introduction to Dynamic Programming on Trees
Dynamic Programming(DP) is a technique to solve problems by breaking them down into overlapping sub-problems which follows the optimal substructure. There are various problems using DP like subset sum, knapsack, coin change etc. DP can also be applied on trees to solve some specific problems.Pre-requisite: DFSGiven a tree with N nodes and N-1 edges
10 min read
Print equal sum sets of Array (Partition Problem) using Dynamic Programming
Given an array arr[]. Determine whether it is possible to split the array into two sets such that the sum of elements in both sets is equal. If it is possible, then print both sets. If it is not possible then output -1. Examples : Input : arr = {5, 5, 1, 11} Output : Set 1 = {5, 5, 1}, Set 2 = {11} Sum of both the sets is 11 and equal. Input : arr
13 min read
Dynamic Programming vs Divide-and-Conquer
In this article I’m trying to explain the difference/similarities between dynamic programming and divide and conquer approaches based on two examples: binary search and minimum edit distance (Levenshtein distance).The ProblemWhen I started to learn algorithms it was hard for me to understand the main idea of dynamic programming (DP) and how it is d
12 min read
Maximum sum of nodes in Binary tree such that no two are adjacent | Dynamic Programming
Given a N-ary tree with a value associated with each node, the task is to choose a subset of these nodes such that sum of chosen nodes is maximum under a constraint that no two chosen node in subset should be directly connected that is, if we have taken a node in our sum then we can’t take its any children in consideration and vice versa.Examples:
9 min read
Distinct palindromic sub-strings of the given string using Dynamic Programming
Given a string str of lowercase alphabets, the task is to find all distinct palindromic sub-strings of the given string. Examples: Input: str = "abaaa" Output: 5 Palindromic sub-strings are "a", "aa", "aaa", "aba" and "b" Input: str = "abcd" Output: 4 Approach: The solution to this problem has been discussed here using Manacher’s algorithm. However
8 min read
Longest path in a directed Acyclic graph | Dynamic Programming
Given a directed graph G with N vertices and M edges. The task is to find the length of the longest directed path in Graph.Note: Length of a directed path is the number of edges in it. Examples: Input: N = 4, M = 5 Output: 3 The directed path 1->3->2->4 Input: N = 5, M = 8 Output: 3 Simple Approach: A naive approach is to calculate the len
8 min read
Count of numbers from range [L, R] whose sum of digits is Y using Dynamic Programming
Pre-requisites: Recursion, Dynamic Programming, Digit DP Given an integer Y and a range [L, R], the task is to find the count of all numbers from the given range whose sum of digits is equal to Y.Examples: Input: L = 0, R = 11, Y = 2 Output: 2 2 -> 2 11 -> 1 + 1 = 2Input: L = 500, R = 1000, Y = 6 Output: 3 Constraints: 0 <= L <= R <=
10 min read
Article Tags :
Practice Tags :
three90RightbarBannerImg