Lunski's Clutter

This is a place to put my clutters, no matter you like it or not, welcome here.

0%

1D Dynamic Programming

一維動態規劃用決策樹分析。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:    
def findTargetSumWays(self, nums: List[int], target: int) -> int:
n = len(nums)
dp = {}
def dfs(i,target):
if (i,target) in dp:
return dp[(i,target)]
if i >= n:
if target == 0:
return 1
else:
return 0
dp[(i,target)] = dfs(i+1,target - nums[i]) + dfs(i+1,target + nums[i])
return dp[(i,target)]
return dfs(0,target)

Image Credits: Neetcode


如果你覺得這篇文章很棒,請你不吝點讚 (゚∀゚)

Welcome to my other publishing channels