Dynamic Programing

Problem Source: Codewars A Hamming number is a positive integer of the form 2i3j5k, for some non-negative integers i, j, and k. Write a function that computes the nth smallest Hamming number. Specifically: The first smallest Hamming number is 1 = 203050 The second smallest Hamming number is 2 = 213050 The third smallest Hamming number is 3 = 203150 The fourth smallest Hamming number is 4 = 223050 The fifth smallest Hamming number is 5 = 203051 The 20 smallest Hamming numbers are given in example test fixture....

Problem Source: Vietnamese: Codeforces - Easy Can be solve with $O(n^2)$ solution Codeforces - Hard Need to be solved in $O(n\log n)$ solution English: Leetcode Give an integer array nums. Return the length of the longest increasing subsequence. An increasing subsequence is a subsequence $a_1,..,a_k$ that $$ \begin{align} &i_1 < i_2 < \dots < i_k,\\\ &nums[i_1] < nums[i_2] < \dots < nums[i_k] \end{align} $$ For example: Input: {0,1,0,3,2,3} Output: 4 //{0,1,2,3} Solution Brute Force This method is the simplest solution can approach: We can enumerate all subsets of the original array and then test them for the increasing property then find the longest....

Problem Source: Codewars From Wikipedia The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to all sequences in a set of sequences. It differs from problems of finding common substrings: unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences. Write a function lcs that accepts two strings and returns their longest common subsequence as a string. Performance matters. For example...

Problem Source: Codewars How many ways can you make the sum of a number? From wikipedia: https://en.wikipedia.org/wiki/Partition_(number_theory)# In number theory and combinatorics, a partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. Example: Input: 4 Output: 5 //4, 3+1, 2+2, 2+1+1, 1+1+1+1 Solution It would be very slow if you enumerate all the partitions when $n$ is large so i’ll use dynamic programing instead (Oω<)☆....

Problem Source: Codeforces Find the $n^th$ Fibonacci number modulo $10^9+7$. So, you need to find $F_n$ in the sequence defined as $$ \begin{aligned} F_0 & = 0\\ F_1 & = 1\\ F_i & = F_{i-1} + F_{i-2} (i >= 2) \end{aligned} $$ Example: Input: 50 Output: 586268941 Solution Approach 1: Dynamic Programing Using fibonacci’s difference equation as a recurrence relation, i can write to a program like this: int f0 = 0, f1 = 1, fn; for(int i = 2; i <= n; i++){ fn = f0 + f1; f0 = f1; f1 = fn; } return fn; This code’s complexity is $O(n)$ which is fine with $n <= 5....

Problem Source: Leetcode , Codewars You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin. For example: Input: amount = 5, coins = {1,2,5} Output: 4 //{5, 2+2+1, 2+1+1+1, 1+1+1+1+1} Solution We’ll go through at each stage to considera certain coin and see how it changes the total amount of ways that can make change....

Problem Source: Leetcode You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1. You may assume that you have an infinite number of each kind of coin. Examples: Input: coins = {1,2,5}, amount = 11 Output: 3 //2 đồng 5 và 1 đồng 1 Input: coins = {2}, amount = 3 Output: -1 Solution Approach 1: Brute force By above example, amount = 11....

Problem: Source: Codewars.com The maximum sum subarray problem consists in finding the maximum sum of a contiguous subsequence in an array or list of integers: maxSequence({-2, 1, -3, 4, -1, 2, 1, -5, 4}); //should be 6: {4, -1, 2, 1} Easy case is when the list is made up of only positive numbers and the maximum sum is the sum of the whole array. If the list is made up of only negative numbers, return 0 instead....