This repository has been archived by the owner on Aug 23, 2023. It is now read-only.
/
CuttingRod.cs
59 lines (49 loc) · 1.49 KB
/
CuttingRod.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace CS.Problems.DynamicProgramming
{
/// <summary>
/// Problem details below
/// http://www.geeksforgeeks.org/dynamic-programming-set-13-cutting-a-rod/
/// </summary>
public class CuttingRod
{
public static int GetMaxProfit(int[] lengths, int[] prices)
{
var priceByLength = new Dictionary<int, int>();
for (int i = 0; i < lengths.Length; i++)
{
priceByLength.Add(lengths[i], prices[i]);
}
return GetMaxProfit(priceByLength, lengths.Length, new Dictionary<int, int>());
}
private static int GetMaxProfit(Dictionary<int, int> priceByLength,
int curLength, Dictionary<int, int> cache)
{
if(curLength < 0)
{
return int.MinValue;
}
if(curLength == 0)
{
return 0;
}
if(cache.ContainsKey(curLength))
{
return cache[curLength];
}
var max = 0;
//get max of cutting at current length
for (int i = 1; i <= curLength; i++)
{
max = Math.Max(max, GetMaxProfit(priceByLength, curLength - i, cache)
+ priceByLength[i]);
}
cache.Add(curLength, max);
return max;
}
}
}