C# DP solution


  • 0
    Y
    //DP 1,2,3,4
    
    public class Solution {
        public int IntegerBreak(int n) {
            int[] DP=new int[n+1];
            DP[2] = 1;
            Dictionary<int,int> cur=new Dictionary<int,int>();
            cur.Add(1,2);
            for(int i=3; i < n + 1; i++)
            {
                if(cur.ContainsKey(1))
                {
                    DP[i] = DP[i-1]*2;
                    cur[1]--;
                    if(cur[1]==0)
                    cur.Remove(1);
                    if(cur.ContainsKey(2))
                        cur[2]++;
                    else
                        cur.Add(2,1);
                }
                else if(cur.ContainsKey(2))
                {
                    DP[i] = DP[i-1] / 2 * 3;
                    cur[2]--;
                    if(cur[2]==0)
                    cur.Remove(2);
                    if(cur.ContainsKey(3))
                        cur[3]++;
                    else
                        cur.Add(3,1);
                }
                else // 3 
                {
                    DP[i] = DP[i-1] / 3 * 4;
                    cur[3]--;
                    if(cur[3]==0)
                    cur.Remove(3);
                    if(cur.ContainsKey(2))
                        cur[2]+=2;
                    else
                        cur.Add(2,2);
                }
            }
            return DP[n];
        }
    }

Log in to reply
 

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