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¶
"""
- Return the number of distinct ways to reach the top of the stairs.
- `dp[n]` stores the number of distinct ways to reach the `n-th` stair.
- Formula: `dp[n] = dp[n - 1] + dp[n - 2]`.
- Initialize `dp[0] = 0`, `dp[1] = 1`, and `dp[2] = 2`.
"""
from functools import cache
# DP
def climbStairsDP(n: int) -> int:
if n <= 2:
return n
dp = [i for i in range(n + 1)]
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
# DP (Optimized)
def climbStairsDPOptimized(n: int) -> int:
if n <= 2:
return n
first, second = 1, 2
for _ in range(3, n + 1):
first, second = second, first + second
return second
# Recursion
def climbStairsRecursion(n: int) -> int:
@cache
def dfs(i: int) -> int:
if i <= 1:
return 1
return dfs(i - 1) + dfs(i - 2)
return dfs(n)
# Greedy
def climbStairsGreedy(n: int) -> int:
if n <= 2:
return n
p1, p2 = 1, 2
for _ in range(3, n + 1):
p1, p2 = p2, p1 + p2
return p2
if __name__ == "__main__":
assert climbStairsDP(10) == 89
assert climbStairsDPOptimized(10) == 89
assert climbStairsRecursion(10) == 89
assert climbStairsGreedy(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¶
"""
- Return the maximum amount of money that can be robbed from the houses. No two adjacent houses can be robbed.
- `dp[n]` stores the maximum amount of money that can be robbed from the first `n` houses.
- Formula: `dp[n] = max(dp[n - 1], dp[n - 2] + nums[n])`.
- Skip: `dp[n]` → `dp[n - 1]`
- Rob: `dp[n]` → `dp[n - 2] + nums[n]`
- Initialize `dp[0] = nums[0]` and `dp[1] = max(nums[0], nums[1])`.
- Return `dp[-1]`.
- Example: `nums = [2, 7, 9, 3, 1]`
| n | `nums[n]` | `dp[n-2]` | `dp[n-1]` | `dp[n-2] + nums[n]` | `dp[n]` |
| :-: | :-------: | :-------: | :-------: | :-----------------: | :-----: |
| 0 | 2 | - | 2 | - | 2 |
| 1 | 7 | - | 7 | - | 7 |
| 2 | 9 | 2 | 7 | 11 | 11 |
| 3 | 3 | 7 | 11 | 10 | 11 |
| 4 | 1 | 11 | 11 | 12 | 12 |
"""
from typing import List
# DP (House Robber)
def rob1(nums: List[int]) -> int:
if len(nums) < 3:
return max(nums)
dp = [0 for _ in range(len(nums))]
dp[0], dp[1] = nums[0], max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
return dp[-1]
# DP (House Robber) Optimized
def rob2(nums: List[int]) -> int:
f0, f1 = 0, 0
for num in nums:
f0, f1 = f1, max(f1, f0 + num)
return f1
nums = [2, 7, 9, 3, 1]
print(rob1(nums)) # 12
print(rob2(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