My C# solution: DFS with cache


  • 0
    G
    public int IntegerBreak(int n) {
        IList<int> results = new List<int>();
        IDictionary<int, int> cache = new Dictionary<int, int>();
        for(int i=2;i<=n;i++)
        {
            int max = 0;
            DFS(results, i, cache, ref max);
            cache[i] = max;
        }
        
        return cache[n];        
    }
    
    
     
    private void DFS(IList<int> path, int target, Dictionary<int, int> cache, ref int max)
    {
      if(target == 0 || cache.ContainsKey(target)) 
      {
          if(target==0 && path.Count==1) return;
          int temp =target==0?1:Math.Max(target, cache[target]);
          foreach (var t in path)
            {
                temp *= t;
            }
            
           max = Math.Max(temp, max); 
           return;
      }
    
        for (int i = 1; i <= target; i++)
        {               
            path.Add(i);
            DFS(path, target - i, cache, ref max);
            path.RemoveAt(path.Count - 1);
        }
    }

Log in to reply
 

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