-
Notifications
You must be signed in to change notification settings - Fork 5
/
DP1.swift
134 lines (124 loc) · 4.97 KB
/
DP1.swift
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
//
// DP1.swift
// AlgorithmsSwift
//
// Created by Michael Ho on 11/12/20.
//
class DP1 {
/**
Methods to find Fibonacci number.
*/
class Fibonacci {
/**
The recursive method to find Fibonacci number. Runtime: O(2^N)
- Parameter n: The number to be calculated Fibonacci numbers.
- Parameter time: The counter to measure runtime.
- Returns: The results of calculation.
*/
func fibonacci(_ n: Int, _ time: inout Int) -> Int {
time += 1
if n == 0 {
return 0
} else if n == 1 || n == 2 {
return 1
} else {
return fibonacci(n - 1, &time) + fibonacci(n - 2, &time)
}
}
/**
The dynamic programming method to find Fibonacci number. Runtime: O(N)
- Parameter n: The number to be calculated Fibonacci numbers.
- Parameter time: The counter to measure runtime.
- Returns: The results of calculation.
*/
func dpFibonacci(_ n: Int, _ time: inout Int) -> Int {
var dp = Array(repeating: 1, count: n + 1)
dp[0] = 0
dp[1] = 1
dp[2] = 1
if n == 0 || n == 1 || n == 2 {
return dp[n]
}
for i in 3...n {
time += 1
dp[i] = dp[i - 1] + dp[i-2]
}
return dp.last!
}
}
/**
A series of longest subsequence problems and their solutions. Subsequence is different from substring. Subsequence is a subset
of elements in order that can be derived from another sequence while substring has to be a set of consecutive elements.
*/
class LongestSubsequence {
/**
The dynamic method used to find the longest length of subsequence. The runtime is O(N^2).
- Parameter array: The input array to find LIS.
- Returns: An integer indicates the length of the longest subsequence.
*/
func findLongestIncreasingSubsequence(_ array: [Int]) -> Int {
var longestLength = 0
var dp = Array(repeating: 0, count: array.count)
dp[0] = 1
for i in 1..<array.count {
dp[i] = 1
for j in 0..<i {
if array[j] < array[i] {
dp[i] = max(dp[i], 1 + dp[j])
}
}
longestLength = max(dp[i], longestLength)
}
return longestLength
}
/**
The dynamic method used to find the longest length of common subsequence of two different string.
The runtime is O(N^2).
Example: https://leetcode.com/problems/uncrossed-lines/
- Parameter string1: The first string.
- Parameter string2: The second string.
- Returns: An integer indicates the length of the longest subsequence.
*/
func findLongestCommonSubsequence(_ string1: String, _ string2: String) -> Int {
let strArr1 = Array(string1)
let strArr2 = Array(string2)
var dp = Array(repeating: Array(repeating: 0, count: strArr2.count), count: strArr1.count)
for i in 0..<dp.count {
/**
Build up the first string. The i in dp means the longest subsequence
we can find until index i in the first string.
*/
for j in 0..<dp[i].count {
/**
Build up the second string. The j in dp means the longest subsequence
we can find until index j in the second string
*/
if strArr1[i] == strArr2[j] {
dp[i][j] = 1
if i > 0, j > 0 {
/**
Since the current one equals to each other, we add it up to the
largest we can find in i - 1 of string1 and j - 1 of string2.
*/
dp[i][j] += dp[i - 1][j - 1]
}
} else {
if j > 0, i > 0 {
/**
If the current ones are not equal, we want to find the largest possible in the
first i - 1 of string1 and first j in string2 or the first i of string1 and
the first j - 1 in string2
*/
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
} else if i > 0 {
dp[i][j] = dp[i - 1][j]
} else if j > 0 {
dp[i][j] = dp[i][j - 1]
}
}
}
}
return dp.last!.last!
}
}
}