codeProblems

binarysearch---rodCutting.py

# https://binarysearch.com/problems/Rod-Cutting
class Solution:
    def solve(self, prices, n):
        
        
        memoRec=[-1]*(n+1)
        def rodCutRec(rodLeft,prices):
            if memoRec[rodLeft]!=-1:
                return memoRec[rodLeft]
            
            if rodLeft == 0:
                return 0
            
            max_val=float('-inf')
            for i,v in enumerate(prices):
                if rodLeft-(i+1) >=0:
                    
                    out=rodCutRec(rodLeft-(i+1),prices)
                    max_val=max(max_val,v+out)
         #calculate the max profit given rod left 
            memoRec[rodLeft]=max_val
            return max_val
            
        
        def rodCutIter(rod_left,prices):
            memo=[0]*(rod_left+1)
            memo[0]=0
            
            for current_len in range(1,rod_left+1):
                for cut_size_minus_one in range(len(prices)):
                    cut_size=cut_size_minus_one+1
                    remaining_len = current_len - cut_size
                    if remaining_len >=0:
                        memo[current_len]=max(memo[current_len],prices[cut_size-1]+memo[remaining_len])
                    
            return memo[rod_left]
                
        
        return rodCutRec(n,prices)
        

binarysearch---rodCutting2.py

# took ~ 50 ish min
# https://binarysearch.com/problems/Rod-Cutting
class Solution:
    def solve(self, prices, n):
        def rodCutItr(prices,n):
            dp=[0]*(n+1)
            dp[0]=0
            
            for curr_len in range(1,n+1):
                for priceIdx in range(len(prices)):
                    if curr_len - (priceIdx+1)>=0:
                        dp[curr_len] = max(dp[curr_len-(priceIdx+1)]+prices[priceIdx],dp[curr_len])
            return dp[n]
        return rodCutItr(prices,n)

leetcode---countVowelStrings.py

class Solution:
    # you need startIdx for this prob
    def countVowelStrings(self, n: int) -> int:
        vowels = ['a','e','i','o','u']
        result=[]
        def cvs(curr,n,startIdx):
            if n==1:
                result.append(curr)
                
                return 1
            
            nways=0
            for i in range(startIdx,5):
                nways+=cvs(curr+vowels[i],n-1,i)
            
            return nways
        total=0
        
        
        memoize=[[-1 for i in range(5)] for i in range(n+1)]
        def cvsMemo(n,startIdx):
            if memoize[n][startIdx]!=-1:
                return memoize[n][startIdx]
                
            if n==1:
                memoize[n][startIdx]=1
                return 1
            
            nways=0
            for i in range(startIdx,5):
                nways+=cvsMemo(n-1,i)
            
            memoize[n][startIdx]=nways
            return nways
        
        cvs=cvsMemo
        for i,v in enumerate(vowels):
            total+=cvs(n,i)
        # print(memoize)
        return total
                
                
            
            
            
        

leetcode---distinctSubseq.py

#https://leetcode.com/problems/distinct-subsequences/

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        
        
        def numberDist(tidx,startIdx):
            
            if tidx==len(t):
                return 1
            total=0
            for i in range(startIdx,len(s)):
                if t[tidx]==s[i]:
                    total+=numberDist(tidx+1,i+1)
            return total
        
        return numberDist(0,0)
            

leetcode---uniquePath.cc

//https://leetcode.com/problems/unique-paths/
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> grid(m);
        for(int i=0;i<m;i++){
            grid[i]=vector<int>(n);
        }
        
        for(int i=0;i<m;i++){
            grid[i][0]=1;
        }
        
        for(int j=0;j<n;j++){
            grid[0][j]=1;
        }
        
        
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                grid[i][j]= grid[i-1][j]+grid[i][j-1];
            }
        }
        return grid[m-1][n-1]
    }
    
    
};