# Tag: dynamic programming

## Find a Fibonacci Number with Matrix Exponentiation

Core Concepts We can represent any number with a power of (2 or 3 or anything). Evidence? The binary system đź™‚ So we can represent any number with log n bits and using 2 as the exponent. f(n) = f(n-1) + f(n-2) => f(n) = 1*f(n-1) + 1*f(n-2) [f(n)] = |1 1| * |f(n-1)| |f(n-2)| We should make the matrix…

## Another Solution: Longest Palindrome Substring

class Solution(object): def __init__(self): self.lookup = {“test”} def isPalindrome(self, s, i, k): j = i + k – 1 if s[i] == s[j]: key = self.createKey(i + 1, j – 1) if key in self.lookup: #self.lookup.remove(key) return True return False def createKey(self, i, j): #return “{}:{}”.format(i,j) #return (i, j) #key = bin(i) + bin(j) #return key key = i +…

## Longest Palindrome Substring in a String

DP based solution class Solution(object): def __init__(self): self.lookup = {} def isPalindrome(self, s, dp, i, k): j = i + k – 1 if s[i] == s[j] and dp[i + 1][j – 1]: return True return False def longestPalindrome(self, s): “”” :type s: str :rtype: str “”” size = len(s) if size < 2: return s dp = [ [False]*size…

## Python Solution: House Robber Problem

class Solution(object): def __init__(self): self.maxVal = 0 self.lookup = {} def rob(self, nums): “”” :type nums: List[int] :rtype: int “”” if len(nums) == 0: return 0 if len(nums) == 1: return nums[0] if len(nums) >= 2: self.lookup[0] = nums[0] self.lookup[1] = max(nums[0], nums[1]) for index in range(2, len(nums)): # There are two options at each house: choose or not choose…