Swift - Dynamic Programming


  • 0
    class Solution {
        func combinationSum4_TopDown(_ nums: [Int], _ target: Int) -> Int {
            var dp = [Int](repeatElement(-1, count: target + 1))
            dp[0] = 1
            return helper(nums, target, &dp)
        }
        
        func helper(_ nums: [Int], _ target: Int, _ dp: inout [Int]) -> Int {
            if dp[target] != -1 {
                return dp[target]
            }
            
            var result = 0
            
            for i in 0..<nums.count {
                if target >= nums[i] {
                    result += helper(nums, target - nums[i], &dp)
                }
            }
            dp[target] = result
            
            return result
        }
        
        func combinationSum4_BottomUp(_ nums: [Int], _ target: Int) -> Int {
            var dp = [Double](repeatElement(0, count: target + 1))
            
            dp[0] = 1
            for i in 1..<dp.count {
                for j in 0..<nums.count {
                    if i - nums[j] >= 0 {
                        dp[i] += dp[i - nums[j]]
                    }
                }
            }
            
            return Int(dp[target])
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.