1D Dynamic Programming¶
Table of Contents¶
- 70. Climbing Stairs (Easy)
- 198. House Robber (Medium)
- 139. Word Break (Medium)
- 322. Coin Change (Medium)
- 300. Longest Increasing Subsequence (Medium)
70. Climbing Stairs¶
from functools import cache
class Solution:
def climbStairs(self, n: int) -> int:
"""Optimized DP: O(n) time, O(1) space.
Only the previous two counts are needed to compute the next stair.
"""
if n <= 2:
return n
first, second = 1, 2
for _ in range(3, n + 1):
first, second = second, first + second
return second
def climbStairsDP(self, n: int) -> int:
"""Tabulation DP: O(n) time, O(n) space.
Each stair count is the sum of the ways to reach the previous two stairs.
"""
if n <= 2:
return n
dp = [0] * (n + 1)
dp[1], dp[2] = 1, 2
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
def climbStairsGreedy(self, n: int) -> int:
"""Greedy Rolling Counts: O(n) time, O(1) space.
The next answer is always determined by the two latest reachable counts.
"""
if n <= 2:
return n
prev, cur = 1, 2
for _ in range(3, n + 1):
prev, cur = cur, prev + cur
return cur
def climbStairsDFS(self, n: int) -> int:
"""Memoized DFS: O(n) time, O(n) space.
Caching prevents recomputing the same remaining-stair subproblems.
"""
@cache
def dfs(i: int) -> int:
if i <= 2:
return i
return dfs(i - 1) + dfs(i - 2)
return dfs(n)
def test_climb_stairs():
s = Solution()
for fn in (
s.climbStairs,
s.climbStairsDP,
s.climbStairsGreedy,
s.climbStairsDFS,
):
assert fn(1) == 1
assert fn(2) == 2
assert fn(3) == 3
assert fn(10) == 89
#include <cassert>
#include <iostream>
using namespace std;
int climbStairs(int n) {
if (n <= 2) return n;
int f1 = 1, f2 = 2;
int res;
int i = 3;
while (i <= n) {
res = f1 + f2;
f1 = f2;
f2 = res;
i++;
}
return res;
}
int main() {
assert(climbStairs(2) == 2);
assert(climbStairs(5) == 8);
assert(climbStairs(10) == 89);
return 0;
}
198. House Robber¶
from functools import cache
from typing import List
class Rob:
"""
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
"""
def incursive(self, nums: List[int]) -> int:
"""
time complexity: O(n)
space complexity: O(n)
"""
n = len(nums)
if n <= 2:
return max(nums)
# init
dp = [0 for _ in range(n)]
dp[0], dp[1] = nums[0], max(nums[0], nums[1])
# update
for i in range(2, n):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
return dp[-1]
def incursive_optimized(self, nums: List[int]) -> int:
"""
time complexity: O(n)
space complexity: O(1)
"""
f0, f1 = 0, 0
for num in nums:
f0, f1 = f1, max(f1, f0 + num)
return f1
def memoization(self, nums: List[int]) -> int:
"""
time complexity: O(n)
space complexity: O(n)
"""
n = len(nums)
@cache
def dp(i: int) -> int:
if i < 0:
return 0
return max(dp(i - 1), dp(i - 2) + nums[i])
return dp(n - 1)
if __name__ == "__main__":
nums = [2, 7, 9, 3, 1]
rob = Rob()
assert rob.incursive(nums) == 12
assert rob.incursive_optimized(nums) == 12
assert rob.memoization(nums) == 12
#include <iostream>
#include <vector>
using namespace std;
int rob(vector<int> &nums) {
int prev = 0, cur = 0, temp = 0;
for (int num : nums) {
temp = cur;
cur = max(cur, prev + num);
prev = temp;
}
return cur;
}
int main() {
vector<int> nums = {2, 7, 9, 3, 1};
cout << rob(nums) << endl; // 12
return 0;
}
139. Word Break¶
from typing import List
# DP (Unbounded Knapsack)
def wordBreak(s: str, wordDict: List[str]) -> bool:
n = len(s)
dp = [False for _ in range(n + 1)]
dp[0] = True
for i in range(1, n + 1):
for word in wordDict:
m = len(word)
if s[i - m : i] == word and dp[i - m]:
dp[i] = True
return dp[-1]
s = "leetcode"
wordDict = ["leet", "code"]
print(wordBreak(s, wordDict)) # True
#include <algorithm>
#include <cassert>
#include <ranges>
#include <string>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
int max_len = ranges::max(wordDict, {}, &string::length).length();
unordered_set<string> words(wordDict.begin(), wordDict.end());
int n = s.length();
vector<int> f(n + 1);
f[0] = true;
for (int i = 1; i <= n; i++) {
for (int j = i - 1; j >= max(i - max_len, 0); j--) {
if (f[j] && words.count(s.substr(j, i - j))) {
f[i] = true;
break;
}
}
}
return f[n];
}
};
int main() {
Solution solution;
string s = "leetcode";
vector<string> wordDict = {"leet", "code"};
assert(solution.wordBreak(s, wordDict) == true);
return 0;
}
322. Coin Change¶
from typing import List
def coinChange(coins: List[int], amount: int) -> int:
dp = [float("inf") for _ in range(amount + 1)]
dp[0] = 0
for i in range(1, amount + 1):
for c in coins:
if i - c >= 0:
dp[i] = min(dp[i], 1 + dp[i - c])
return dp[amount] if dp[amount] != float("inf") else -1
coins = [1, 2, 5]
amount = 11
print(coinChange(coins, amount)) # 3
300. Longest Increasing Subsequence¶
from functools import cache
from typing import List
# DP - LIS
def lengthOfLISMemo(nums: List[int]) -> int:
n = len(nums)
if n <= 1:
return n
@cache
def dfs(i: int) -> int:
res = 0
for j in range(i):
if nums[j] < nums[i]:
res = max(res, dfs(j))
return res + 1
return max(dfs(i) for i in range(n))
# DP - LIS
def lengthOfLISTable(nums: List[int]) -> int:
n = len(nums)
if n <= 1:
return n
dp = [1 for _ in range(n)]
for i in range(n):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
if __name__ == "__main__":
assert lengthOfLISMemo([10, 9, 2, 5, 3, 7, 101, 18]) == 4
assert lengthOfLISTable([10, 9, 2, 5, 3, 7, 101, 18]) == 4
assert lengthOfLISMemo([0, 1, 0, 3, 2, 3]) == 4
assert lengthOfLISTable([0, 1, 0, 3, 2, 3]) == 4
assert lengthOfLISMemo([7, 7, 7, 7]) == 1
assert lengthOfLISTable([7, 7, 7, 7]) == 1