Rod of length - Feb. 23, 20210 - mock interview as an interviewee

rod of length

Rod of length L
prices for each length 

We want to find the the most optimum way of cutting the rod, so that the optimize on the max price. 
    
    5
shorter one, cheap -> 
    1 + 1 + 3 = 5 + 5 + 5.5 = 15.5
    
    2 + 2 +1 = 4 + 4 + 5 = 13
    
    [4, 1] 5 + 5 = 10
    brute force: 
5
maximum one - all combination one: dp[5] 
subproblem - dynamic 
    dp[5] = (dp[4] + dp[1]) case 1
             dp[3] + dp[2]  case 2
         5 cases 
             dp[1] + dp[4]  case 4 - case 1 and case 4
    
      Maximum(case1 to case 5)
    bottom up dp[1]
    
    dp[0] = 0; 
    dp[1] -> definition 
    dp[n] = Maximum ( for i = 1 to n - 1, dp[n - i], dp[i]
    
    dp[4]
    dp[3]
    dp[2]
    dp[1]
  find dp[1], dp[2], ... dp[5]
    
    5 total length
        
    1 - 5 
    2 - 4
    3 - 5.5
    4: 5
    5: 6
                     
                     
   1 - 5 
   2 - [4, dp[1] + dp[1] = 10,] -> 10
   3 - [5.5, dp[2] + dp[1], dp[1] + dp[2], dp[1]+dp[1]+dp[1] ]  
             ------------>        
                     
  dp[n] - maximum price for rod length of n 
  
 dp[0] 
 
  0 1  2  3 4  5  (total length)                   <- n length
----------------                     
1 0 5 10 15 20 25                  
2 0 5 10  15 
3                     
4                     argue that at most 2 subproblems enough to solve 
5                     dp[i - 1] -> i - 1, extra 1 foot -> price

y-axis : cuts

voice breaking a lot

? - max[10, 4 ]= 10
                          max[15, 4 + dp(upto 2, 1) = 5)
                        max[20,4 + dp[upto 2,2)= 14] -> 20

considering only the cuts upto i -1 
                     
                     dp[cut option, total length]
                        i - 1,     
2  max(dp(1) + 4, dp(i-1)) -> work on 2 foot, 
3
4
5
        calculateMaxPrice(int[] price)
                            {
                var length = price.Length; 
                var dp = new int[length, length];
                // row will be cut                
                for(int row = 1; row < length; row++)