Skip to main content

Distinct subsequences using dynamic programming

Here given code implementation process.

// C Program
// Distinct subsequences using dynamic programming
#include <stdio.h>

#include <string.h>

void distinctSubsequences(char *sequence, char *word)
{
	// Get the length of sequence
	int n = strlen(sequence);
	// Get the length of word
	int m = strlen(word);
	int dp[n + 1][m + 1];
	// Set initial value of first column
	for (int i = 0; i <= n; ++i)
	{
		dp[i][0] = 1;
	}
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			if (sequence[i] == word[j])
			{
				// Change value when sequence contains word element
				dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1];
			}
			else
			{
				dp[i + 1][j + 1] = dp[i][j + 1];
			}
		}
	}
	// Display given data
	printf("\n Sequence : %s ", sequence);
	printf("\n Word : %s", word);
	// Display calculated result
	printf("\n Result : %d", dp[n][m]);
}
int main()
{
	char *sequence = "initcometipe";
	char *word = "ice";
	/*
	    sequence : initcometipe
	    word     : ice
	    ------------------
	        initcometipe 
	        -   -  -        ➀ [ice]
	        
	        initcometipe 
	        -   -      -    ➁ [ice]

	        initcometipe 
	          - -  -        ➂ [ice]
	        
	        initcometipe 
	          - -      -    ➃ [ice]
	    -------------------------------
	    4 possible sequence
	*/
	distinctSubsequences(sequence, word);
	return 0;
}

Output

 Sequence : initcometipe
 Word : ice
 Result : 4
// Java program for
// Distinct subsequences using dynamic programming
public class Subsequence
{
	public void distinctSubsequences(String sequence, String word)
	{
		// Get the length of sequence
		int n = sequence.length();
		// Get the length of word
		int m = word.length();
		int[][] dp = new int[n + 1][m + 1];
		// Set initial value of first column
		for (int i = 0; i <= n; ++i)
		{
			dp[i][0] = 1;
		}
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < m; ++j)
			{
				if (sequence.charAt(i) == word.charAt(j))
				{
					// Change value when sequence contains word element
					dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1];
				}
				else
				{
					dp[i + 1][j + 1] = dp[i][j + 1];
				}
			}
		}
		// Display given data
		System.out.print("\n Sequence : " + sequence);
		System.out.print("\n Word : " + word);
		// Display calculated result
		System.out.print("\n Result : " + dp[n][m]);
	}
	public static void main(String[] args)
	{
		Subsequence task = new Subsequence();
		String sequence = "initcometipe";
		String word = "ice";
		/*
		    sequence : initcometipe
		    word     : ice
		    ------------------
		        initcometipe 
		        -   -  -        ➀ [ice]
		        
		        initcometipe 
		        -   -      -    ➁ [ice]

		        initcometipe 
		          - -  -        ➂ [ice]
		        
		        initcometipe 
		          - -      -    ➃ [ice]
		    -------------------------------
		    4 possible sequence
		*/
		task.distinctSubsequences(sequence, word);
	}
}

Output

 Sequence : initcometipe
 Word : ice
 Result : 4
// Include header file
#include <iostream>

#include <string>

using namespace std;
// C++ program for
// Distinct subsequences using dynamic programming
class Subsequence
{
	public: void distinctSubsequences(string sequence, string word)
	{
		// Get the length of sequence
		int n = sequence.length();
		// Get the length of word
		int m = word.length();
		int dp[n + 1][m + 1];
		// Set initial value of first column
		for (int i = 0; i <= n; ++i)
		{
			dp[i][0] = 1;
		}
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < m; ++j)
			{
				if (sequence[i] == word[j])
				{
					// Change value when sequence contains word element
					dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1];
				}
				else
				{
					dp[i + 1][j + 1] = dp[i][j + 1];
				}
			}
		}
		// Display given data
		cout << "\n Sequence : " << sequence;
		cout << "\n Word : " << word;
		// Display calculated result
		cout << "\n Result : " << dp[n][m];
	}
};
int main()
{
	Subsequence *task = new Subsequence();
	string sequence = "initcometipe";
	string word = "ice";
	/*
	    sequence : initcometipe
	    word     : ice
	    ------------------
	        initcometipe 
	        -   -  -        ➀ [ice]
	        
	        initcometipe 
	        -   -      -    ➁ [ice]
	        initcometipe 
	          - -  -        ➂ [ice]
	        
	        initcometipe 
	          - -      -    ➃ [ice]
	    -------------------------------
	    4 possible sequence
	*/
	task->distinctSubsequences(sequence, word);
	return 0;
}

Output

 Sequence : initcometipe
 Word : ice
 Result : 4
// Include namespace system
using System;
// Csharp program for
// Distinct subsequences using dynamic programming
public class Subsequence
{
	public void distinctSubsequences(String sequence, String word)
	{
		// Get the length of sequence
		int n = sequence.Length;
		// Get the length of word
		int m = word.Length;
		int[,] dp = new int[n + 1,m + 1];
		// Set initial value of first column
		for (int i = 0; i <= n; ++i)
		{
			dp[i,0] = 1;
		}
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < m; ++j)
			{
				if (sequence[i] == word[j])
				{
					// Change value when sequence contains word element
					dp[i + 1,j + 1] = dp[i,j] + dp[i,j + 1];
				}
				else
				{
					dp[i + 1,j + 1] = dp[i,j + 1];
				}
			}
		}
		// Display given data
		Console.Write("\n Sequence : " + sequence);
		Console.Write("\n Word : " + word);
		// Display calculated result
		Console.Write("\n Result : " + dp[n,m]);
	}
	public static void Main(String[] args)
	{
		Subsequence task = new Subsequence();
		String sequence = "initcometipe";
		String word = "ice";
		/*
		    sequence : initcometipe
		    word     : ice
		    ------------------
		        initcometipe 
		        -   -  -        ➀ [ice]
		        
		        initcometipe 
		        -   -      -    ➁ [ice]
		        initcometipe 
		          - -  -        ➂ [ice]
		        
		        initcometipe 
		          - -      -    ➃ [ice]
		    -------------------------------
		    4 possible sequence
		*/
		task.distinctSubsequences(sequence, word);
	}
}

Output

 Sequence : initcometipe
 Word : ice
 Result : 4
package main
import "fmt"
// Go program for
// Distinct subsequences using dynamic programming

func distinctSubsequences(sequence, word string) {
	// Get the length of sequence
	var n int = len(sequence)
	// Get the length of word
	var m int = len(word)
	var dp = make([][] int, n + 1)
	for i:= 0; i < n + 1;i++ {
		dp[i] = make([]int,m+1)
	}
	// Set initial value of first column
	for i := 0 ; i <= n ; i++ {
		dp[i][0] = 1
	}
	for i := 0 ; i < n ; i++ {
		for j := 0 ; j < m ; j++ {
			if sequence[i] == word[j] {
				// Change value when sequence contains word element
				dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1]
			} else {
				dp[i + 1][j + 1] = dp[i][j + 1]
			}
		}
	}
	// Display given data
	fmt.Print("\n Sequence : ", sequence)
	fmt.Print("\n Word : ", word)
	// Display calculated result
	fmt.Print("\n Result : ", dp[n][m])
}
func main() {

	var sequence string = "initcometipe"
	var word string = "ice"
	/*
	    sequence : initcometipe
	    word     : ice
	    ------------------
	        initcometipe 
	        -   -  -        ➀ [ice]
	        
	        initcometipe 
	        -   -      -    ➁ [ice]
	        initcometipe 
	          - -  -        ➂ [ice]
	        
	        initcometipe 
	          - -      -    ➃ [ice]
	    -------------------------------
	    4 possible sequence
	*/
	distinctSubsequences(sequence, word)
}

Output

 Sequence : initcometipe
 Word : ice
 Result : 4
<?php
// Php program for
// Distinct subsequences using dynamic programming
class Subsequence
{
	public	function distinctSubsequences($sequence, $word)
	{
		// Get the length of sequence
		$n = strlen($sequence);
		// Get the length of word
		$m = strlen($word);
		$dp = array_fill(0, $n + 1, array_fill(0, $m + 1, 0));
		// Set initial value of first column
		for ($i = 0; $i <= $n; ++$i)
		{
			$dp[$i][0] = 1;
		}
		for ($i = 0; $i < $n; ++$i)
		{
			for ($j = 0; $j < $m; ++$j)
			{
				if ($sequence[$i] == $word[$j])
				{
					// Change value when sequence contains word element
					$dp[$i + 1][$j + 1] = $dp[$i][$j] + $dp[$i][$j + 1];
				}
				else
				{
					$dp[$i + 1][$j + 1] = $dp[$i][$j + 1];
				}
			}
		}
		// Display given data
		echo("\n Sequence : ".$sequence);
		echo("\n Word : ".$word);
		// Display calculated result
		echo("\n Result : ".$dp[$n][$m]);
	}
}

function main()
{
	$task = new Subsequence();
	$sequence = "initcometipe";
	$word = "ice";
	/*
	    sequence : initcometipe
	    word     : ice
	    ------------------
	        initcometipe 
	        -   -  -        ➀ [ice]
	        
	        initcometipe 
	        -   -      -    ➁ [ice]
	        initcometipe 
	          - -  -        ➂ [ice]
	        
	        initcometipe 
	          - -      -    ➃ [ice]
	    -------------------------------
	    4 possible sequence
	*/
	$task->distinctSubsequences($sequence, $word);
}
main();

Output

 Sequence : initcometipe
 Word : ice
 Result : 4
// Node JS program for
// Distinct subsequences using dynamic programming
class Subsequence
{
	distinctSubsequences(sequence, word)
	{
		// Get the length of sequence
		var n = sequence.length;
		// Get the length of word
		var m = word.length;
		var dp = Array(n + 1).fill(0).map(() => new Array(m + 1).fill(0));
		// Set initial value of first column
		for (var i = 0; i <= n; ++i)
		{
			dp[i][0] = 1;
		}
		for (var i = 0; i < n; ++i)
		{
			for (var j = 0; j < m; ++j)
			{
				if (sequence.charAt(i) == word.charAt(j))
				{
					// Change value when sequence contains word element
					dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1];
				}
				else
				{
					dp[i + 1][j + 1] = dp[i][j + 1];
				}
			}
		}
		// Display given data
		process.stdout.write("\n Sequence : " + sequence);
		process.stdout.write("\n Word : " + word);
		// Display calculated result
		process.stdout.write("\n Result : " + dp[n][m]);
	}
}

function main()
{
	var task = new Subsequence();
	var sequence = "initcometipe";
	var word = "ice";
	/*
	    sequence : initcometipe
	    word     : ice
	    ------------------
	        initcometipe 
	        -   -  -        ➀ [ice]
	        
	        initcometipe 
	        -   -      -    ➁ [ice]
	        initcometipe 
	          - -  -        ➂ [ice]
	        
	        initcometipe 
	          - -      -    ➃ [ice]
	    -------------------------------
	    4 possible sequence
	*/
	task.distinctSubsequences(sequence, word);
}
main();

Output

 Sequence : initcometipe
 Word : ice
 Result : 4
#  Python 3 program for
#  Distinct subsequences using dynamic programming
class Subsequence :
	def distinctSubsequences(self, sequence, word) :
		#  Get the length of sequence
		n = len(sequence)
		#  Get the length of word
		m = len(word)
		dp = [[0] * (m + 1) for _ in range(n + 1) ]
		i = 0
		#  Set initial value of first column
		while (i <= n) :
			dp[i][0] = 1
			i += 1
		
		i = 0
		while (i < n) :
			j = 0
			while (j < m) :
				if (sequence[i] == word[j]) :
					#  Change value when sequence contains word element
					dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1]
				else :
					dp[i + 1][j + 1] = dp[i][j + 1]
				
				j += 1
			
			i += 1
		
		#  Display given data
		print("\n Sequence : ", sequence, end = "")
		print("\n Word : ", word, end = "")
		#  Display calculated result
		print("\n Result : ", dp[n][m], end = "")
	

def main() :
	task = Subsequence()
	sequence = "initcometipe"
	word = "ice"
	#    sequence : initcometipe
	#    word     : ice
	#    ------------------
	#        initcometipe 
	#        -   -  -        ➀ [ice]
	#        initcometipe 
	#        -   -      -    ➁ [ice]
	#        initcometipe 
	#          - -  -        ➂ [ice]
	#        initcometipe 
	#          - -      -    ➃ [ice]
	#    -------------------------------
	#    4 possible sequence
	task.distinctSubsequences(sequence, word)

if __name__ == "__main__": main()

Output

 Sequence :  initcometipe
 Word :  ice
 Result :  4
#  Ruby program for
#  Distinct subsequences using dynamic programming
class Subsequence 
	def distinctSubsequences(sequence, word) 
		#  Get the length of sequence
		n = sequence.length
		#  Get the length of word
		m = word.length
		dp = Array.new(n + 1) {Array.new(m + 1) {0}}
		i = 0
		#  Set initial value of first column
		while (i <= n) 
			dp[i][0] = 1
			i += 1
		end

		i = 0
		while (i < n) 
			j = 0
			while (j < m) 
				if (sequence[i] == word[j]) 
					#  Change value when sequence contains word element
					dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1]
				else
 
					dp[i + 1][j + 1] = dp[i][j + 1]
				end

				j += 1
			end

			i += 1
		end

		#  Display given data
		print("\n Sequence : ", sequence)
		print("\n Word : ", word)
		#  Display calculated result
		print("\n Result : ", dp[n][m])
	end

end

def main() 
	task = Subsequence.new()
	sequence = "initcometipe"
	word = "ice"
	#    sequence : initcometipe
	#    word     : ice
	#    ------------------
	#        initcometipe 
	#        -   -  -        ➀ [ice]
	#        initcometipe 
	#        -   -      -    ➁ [ice]
	#        initcometipe 
	#          - -  -        ➂ [ice]
	#        initcometipe 
	#          - -      -    ➃ [ice]
	#    -------------------------------
	#    4 possible sequence
	task.distinctSubsequences(sequence, word)
end

main()

Output

 Sequence : initcometipe
 Word : ice
 Result : 4
import scala.collection.mutable._;
// Scala program for
// Distinct subsequences using dynamic programming
class Subsequence()
{
	def distinctSubsequences(sequence: String, word: String): Unit = {
		// Get the length of sequence
		var n: Int = sequence.length();
		// Get the length of word
		var m: Int = word.length();
		var dp: Array[Array[Int]] = Array.fill[Int](n + 1, m + 1)(0);
		var i: Int = 0;
		// Set initial value of first column
		while (i <= n)
		{
			dp(i)(0) = 1;
			i += 1;
		}
		i = 0;
		while (i < n)
		{
			var j: Int = 0;
			while (j < m)
			{
				if (sequence.charAt(i) == word.charAt(j))
				{
					// Change value when sequence contains word element
					dp(i + 1)(j + 1) = dp(i)(j) + dp(i)(j + 1);
				}
				else
				{
					dp(i + 1)(j + 1) = dp(i)(j + 1);
				}
				j += 1;
			}
			i += 1;
		}
		// Display given data
		print("\n Sequence : " + sequence);
		print("\n Word : " + word);
		// Display calculated result
		print("\n Result : " + dp(n)(m));
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Subsequence = new Subsequence();
		var sequence: String = "initcometipe";
		var word: String = "ice";
		/*
		    sequence : initcometipe
		    word     : ice
		    ------------------
		        initcometipe 
		        -   -  -        ➀ [ice]
		        
		        initcometipe 
		        -   -      -    ➁ [ice]
		        initcometipe 
		          - -  -        ➂ [ice]
		        
		        initcometipe 
		          - -      -    ➃ [ice]
		    -------------------------------
		    4 possible sequence
		*/
		task.distinctSubsequences(sequence, word);
	}
}

Output

 Sequence : initcometipe
 Word : ice
 Result : 4
import Foundation;
// Swift 4 program for
// Distinct subsequences using dynamic programming
class Subsequence
{
	func distinctSubsequences(_ s: String, _ w: String)
	{
      	let sequence = Array(s);
      	let word = Array(w);
		// Get the length of sequence
		let n: Int = sequence.count;
		// Get the length of word
		let m: Int = word.count;
		var dp: [[Int]] = 
          Array(repeating: Array(repeating: 0, count: m + 1), count: n + 1);
		var i: Int = 0;
		// Set initial value of first column
		while (i <= n)
		{
			dp[i][0] = 1;
			i += 1;
		}
		i = 0;
		while (i < n)
		{
			var j: Int = 0;
			while (j < m)
			{
				if (sequence[i] == word[j])
				{
					// Change value when sequence contains word element
					dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1];
				}
				else
				{
					dp[i + 1][j + 1] = dp[i][j + 1];
				}
				j += 1;
			}
			i += 1;
		}
		// Display given data
		print("\n Sequence : ", s, terminator: "");
		print("\n Word : ", w, terminator: "");
		// Display calculated result
		print("\n Result : ", dp[n][m], terminator: "");
	}
}
func main()
{
	let task: Subsequence = Subsequence();
	let sequence: String = "initcometipe";
	let word: String = "ice";
	/*
	    sequence : initcometipe
	    word     : ice
	    ------------------
	        initcometipe 
	        -   -  -        ➀ [ice]
	        
	        initcometipe 
	        -   -      -    ➁ [ice]
	        initcometipe 
	          - -  -        ➂ [ice]
	        
	        initcometipe 
	          - -      -    ➃ [ice]
	    -------------------------------
	    4 possible sequence
	*/
	task.distinctSubsequences(sequence, word);
}
main();

Output

 Sequence :  initcometipe
 Word :  ice
 Result :  4
// Kotlin program for
// Distinct subsequences using dynamic programming
class Subsequence
{
	fun distinctSubsequences(sequence: String, word: String): Unit
	{
		// Get the length of sequence
		val n: Int = sequence.length;
		// Get the length of word
		val m: Int = word.length;
		var dp: Array < Array < Int >> = Array(n + 1)
		{
			Array(m + 1)
			{
				0
			}
		};
		var i: Int = 0;
		// Set initial value of first column
		while (i <= n)
		{
			dp[i][0] = 1;
			i += 1;
		}
		i = 0;
		while (i < n)
		{
			var j: Int = 0;
			while (j < m)
			{
				if (sequence.get(i) == word.get(j))
				{
					// Change value when sequence contains word element
					dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1];
				}
				else
				{
					dp[i + 1][j + 1] = dp[i][j + 1];
				}
				j += 1;
			}
			i += 1;
		}
		// Display given data
		print("\n Sequence : " + sequence);
		print("\n Word : " + word);
		// Display calculated result
		print("\n Result : " + dp[n][m]);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Subsequence = Subsequence();
	val sequence: String = "initcometipe";
	val word: String = "ice";
	/*
	    sequence : initcometipe
	    word     : ice
	    ------------------
	        initcometipe 
	        -   -  -        ➀ [ice]
	        
	        initcometipe 
	        -   -      -    ➁ [ice]
	        initcometipe 
	          - -  -        ➂ [ice]
	        
	        initcometipe 
	          - -      -    ➃ [ice]
	    -------------------------------
	    4 possible sequence
	*/
	task.distinctSubsequences(sequence, word);
}

Output

 Sequence : initcometipe
 Word : ice
 Result : 4
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment