Skip to content

Commit 4d5fe57

Browse files
author
Мето Трајковски
committed
Added dynamic programming solutions.
1 parent 33e9a39 commit 4d5fe57

4 files changed

Lines changed: 204 additions & 2 deletions

File tree

‎Dynamic Programming/number_of_decodings.py‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
'''
2-
Number of decodings
2+
Number of Decodings
33
44
Given the mapping a=1, b=2, ... , z=26, and an encoded message, count the number of ways it can be decoded.
55
For example, the message "111" would give 3, since it could be decoded as "aaa", "ka" and "ak".
@@ -9,7 +9,7 @@
99
The easiest solution is Brute-Force (building a tree and making all combinations),
1010
and in the worst case there will be Fibbionaci(N) combinations, so the worst Time Complexity will be O(Fib(N))
1111
12-
Dynamic programming solution.
12+
Dynamic programming solution. Similar to number_of_smses.py.
1313
Time Complexity: O(N)
1414
Space Complexity: O(N)
1515
'''

‎Dynamic Programming/number_of_smses.py‎

Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,84 @@
1+
'''
2+
Number of SMSes
3+
4+
Given the number sequence that is being typed in order to write and SMS message, return the count
5+
of all the possible messages that can be constructed.
6+
7+
1 2 3
8+
abc def
9+
10+
4 5 6
11+
ghi jkl mno
12+
13+
7 8 9
14+
pqrs tuv wxyz
15+
16+
The blank space character is constructed with a '0'.
17+
18+
Input: '222'
19+
Output: 4
20+
Output explanation: '222' could mean: 'c', 'ab','ba' or 'aaa'. That makes 4 possible messages.
21+
22+
=========================================
23+
Dynamic programming solution. Similar to number_of_decodings.py.
24+
Time Complexity: O(N)
25+
Space Complexity: O(N)
26+
'''
27+
28+
29+
############
30+
# Solution #
31+
############
32+
33+
def num_smses(sequence):
34+
n = len(sequence)
35+
dp = [0] * n
36+
37+
# dp starting values, check all 4 possible starting combinations
38+
for i in range(min(4, n)):
39+
if is_valid(sequence[0 : i+1]):
40+
dp[i] = 1
41+
42+
# run dp
43+
for i in range(1, n):
44+
# check all 4 possible combinations (x, xx, xxx, xxxx)
45+
for j in range(min(4, i)):
46+
if is_valid(sequence[i-j : i+1]):
47+
dp[i] += dp[i - j - 1]
48+
49+
return dp[n - 1]
50+
51+
def is_valid(sequence):
52+
ch = sequence[0]
53+
54+
for c in sequence:
55+
if c != ch:
56+
return False
57+
58+
if sequence == '0':
59+
return True
60+
61+
if ((ch >= '2' and ch <= '6') or ch == '8') and (len(sequence) < 4):
62+
return True
63+
64+
if (ch == '7') or (ch == '9'):
65+
return True
66+
67+
return False
68+
69+
70+
###########
71+
# Testing #
72+
###########
73+
74+
# Test 1
75+
# Correct result => 4
76+
print(num_smses('222'))
77+
78+
# Test 2
79+
# Correct result => 14
80+
print(num_smses('2202222'))
81+
82+
# Test 3
83+
# Correct result => 274
84+
print(num_smses('2222222222'))

‎Dynamic Programming/ordered_digits.py‎

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
'''
2+
Ordered Digits
3+
4+
We are given a number and we need to transform to a new number where all its digits are ordered in a non descending order.
5+
We are allowed to increase or decrease a digit by 1, and each of those actions counts as one operation.
6+
We are also allowed to over/underflow a number meaning from '9' we can change to '0' and also from '0' to '9', also costing only one operation.
7+
One same digit can be changed multiple times.
8+
Find the minimum number of operations we need to do do to create a new number with its ordered digits.
9+
10+
Input: 301
11+
Output: 3
12+
Output explanation: 301 -> 201 -> 101 -> 111, in this case 3 operations are required to get an ordered number.
13+
14+
Input: 901
15+
Output: 1
16+
Output explanation: 901 -> 001, in this case 1 operation is required to get an ordered number.
17+
18+
Input: 5982
19+
Output: 4
20+
Output explanation: 5982 -> 5981 -> 5980 -> 5989 -> 5999, in this case 4 operations are required to get an ordered number.
21+
22+
=========================================
23+
Dynamic programming solution. For each position, calculate the cost of transformation to each possible digit (0-9).
24+
And take the minimum value from the previous position (but smaller than the current digit).
25+
Time Complexity: O(N) , O(N*10) = O(N), N = number of digits
26+
Space Complexity: O(N) , same O(N*2) = O(N)
27+
'''
28+
29+
30+
############
31+
# Solution #
32+
############
33+
34+
def ordered_digits(number):
35+
n = len(number)
36+
dp = [[0 for j in range(10)] for i in range(2)]
37+
38+
for i in range(n):
39+
min_prev = float('inf')
40+
for j in range(10):
41+
# find the min value from the previous digit and add it to the current value
42+
min_prev = min(min_prev, dp[(i - 1) % 2][j])
43+
# compute diff between the current digit and wanted digit
44+
diff = abs(j - int(number[i]))
45+
dp[i % 2][j] = min(diff, 10 - diff) + min_prev
46+
47+
# min value from the last digit
48+
return min(dp[(n - 1) % 2])
49+
50+
51+
###########
52+
# Testing #
53+
###########
54+
55+
# Test 1
56+
# Correct result => 3
57+
print(ordered_digits('301'))
58+
59+
# Test 2
60+
# Correct result => 1
61+
print(ordered_digits('901'))
62+
63+
# Test 3
64+
# Correct result => 4
65+
print(ordered_digits('5982'))

‎Dynamic Programming/split_coins.py‎

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
'''
2+
Split Coins
3+
4+
You have a number of coins with various amounts.
5+
You need to split the coins in two groups so that the difference between those groups in minimal.
6+
7+
Input: [1, 1, 1, 3, 5, 10, 18]
8+
Output: 1
9+
Output explanation: First group 1, 3, 5, 10 (or 1, 1, 3, 5, 10) and second group 1, 1, 18 (or 1, 18).
10+
11+
=========================================
12+
Simple dynamic programming solution. Find the closest sum to the half of the sum of all coins.
13+
Time Complexity: O(C*HS) , C = number of coins, HS = half of the sum of all coins
14+
Space Complexity: O(HS)
15+
'''
16+
17+
18+
############
19+
# Solution #
20+
############
21+
22+
def split_coins(coins):
23+
if len(coins) == 0:
24+
return -1
25+
26+
full_sum = sum(coins)
27+
half_sum = full_sum // 2 + 1
28+
29+
dp = [False]*half_sum
30+
dp[0] = True
31+
32+
for c in coins:
33+
for i in range(half_sum - 1, -1, -1):
34+
if (i >= c) and dp[i - c]:
35+
# if you want to find coins, save the coin here dp[i] = c
36+
dp[i] = True
37+
38+
for i in range(half_sum - 1, -1, -1):
39+
if dp[i]:
40+
# if you want to print coins, while i>0: print(dp[i]) i -= dp[i]
41+
return full_sum - 2 * i
42+
43+
# not possible
44+
return -1
45+
46+
47+
###########
48+
# Testing #
49+
###########
50+
51+
# Test 1
52+
# Correct result => 1
53+
print(split_coins([1, 1, 1, 3, 5, 10, 18]))

0 commit comments

Comments
 (0)