coin change Dynamic Programming done!

1 files changed, 19 insertions, 158 deletions

diff --git a/PlaygroundCpp/Sources/Playground.cpp b/PlaygroundCpp/Sources/Playground.cpp
index d3330a1..070cf04 100644
--- a/PlaygroundCpp/Sources/Playground.cpp
+++ b/PlaygroundCpp/Sources/Playground.cpp
@@ -1,171 +1,32 @@
 #include <iostream>
-#include <vector>
-#include <cmath>
-#include <iomanip>
-#include <algorithm>
-#include <cfloat>
+#include <climits>
 //#include <gtest/gtest.h>
 
-using std::vector;
-using std::min;
-
-struct Point {
-	int x, y;
-	bool operator==(const Point &p1) {
-		return (x == p1.x && y == p1.y);
-	}
-};
-
-bool sortPointXDimension(Point i, Point j) {
-	if (i.x == j.x) {
-		return i.y < j.y;
-	}
-	return i.x < j.x;
-}
-
-bool sortPointYDimension(Point i, Point j) {
-	if (i.y == j.y) {
-		return i.x < j.x;
-	}
-	return i.y < j.y;
-}
-
-float distance(Point p1, Point p2) {
-	return pow(p1.x - p2.x, 2) + pow(p1.y - p2.y, 2);
-}
-
-float baseCaseMinDistance(vector<Point> &ptsVector, int low, int high) {
-	if (high - low == 1)
-		return distance(ptsVector[low], ptsVector[high]);
-	if (high - low == 2) {
-		float f1 = distance(ptsVector[low], ptsVector[low + 1]);
-		float f2 = distance(ptsVector[low], ptsVector[high]);
-		float f3 = distance(ptsVector[high], ptsVector[low + 1]);
-		return min(f1, min(f2, f3));
-	}
-	float f1 = distance(ptsVector[low], ptsVector[low + 1]);
-	float f2 = distance(ptsVector[low], ptsVector[low + 2]);
-	float f3 = distance(ptsVector[low], ptsVector[high]);
-	float f4 = distance(ptsVector[low + 1], ptsVector[low + 2]);
-	float f5 = distance(ptsVector[low + 1], ptsVector[high]);
-	float f6 = distance(ptsVector[low + 2], ptsVector[high]);
-	return min(f1, min(f2, min(f3, min(f4, min(f5, f6)))));
-}
-
-float dPrimeDistance(vector<Point> &shadedPoints) {
-	float minDistance = FLT_MAX;
-	float tempDistance;
-	for (int i = 0; i < shadedPoints.size(); i++) {
-		for (int j = 1; j <= 5; j++) {
-			if (i + j < shadedPoints.size()) {
-				tempDistance = distance(shadedPoints[i], shadedPoints[i + j]);
-				minDistance = min(tempDistance, minDistance);
+int getChange(int money) {
+	// denominations: 1, 3, 4
+	int denominations[3] = { 1, 3, 4 };
+	int minNumCoins[money + 1] = { };
+	for (int m = 1; m < money + 1; m++) {
+		minNumCoins[m] = INT_MAX;
+		for (int i = 0; i < 3; i++) {
+			if (m >= denominations[i]) {
+				int numCoins = minNumCoins[m - denominations[i]] + 1;
+				if (numCoins < minNumCoins[m]) {
+					minNumCoins[m] = numCoins;
+				}
 			}
 		}
 	}
-	return minDistance;
+	return minNumCoins[money];
 }
 
-float minimalDistance(vector<Point> &ptsVector, int low, int high) {
-	if (high - low <= 3) {
-		return baseCaseMinDistance(ptsVector, low, high);
-	}
-	int mid = low + (high - low) / 2;
-	long midX = ptsVector[mid].x;
-	float f1 = minimalDistance(ptsVector, low, mid - 1);
-	float f2 = minimalDistance(ptsVector, mid, high);
-	float f = min(f1, f2);
-	vector<Point> shadedPoints;
-	for (int i = low; i <= high; i++) {
-		if (abs(ptsVector[i].x - midX) <= f)
-			shadedPoints.push_back(ptsVector[i]);
-	}
-
-	std::sort(shadedPoints.begin(), shadedPoints.end(), sortPointYDimension);
-
-	float fPrime = dPrimeDistance(shadedPoints);
-
-	return min(f, fPrime);
-}
-float minimalDistance(vector<int> &x, vector<int> &y) {
-	vector<Point> ptsVector(x.size());
-	Point tempP;
-
-	for (int i = 0; i < x.size(); i++) {
-		tempP = {x[i],y[i]};
-		ptsVector[i] = tempP;
-	}
-
-	std::sort(ptsVector.begin(), ptsVector.end(), sortPointXDimension);
-	return sqrt(minimalDistance(ptsVector, 0, ptsVector.size() - 1));
-}
 //TEST(SortPoint, Sort1) {
-//	vector<int> x = { 4, -2, -3, -1, 2, -4, 1, -1, 3, -4, -2 };
-//	vector<int> y = { 4, -2, -4, 3, 3, 0, 1, -1, -1, 2, 4 };
-//	vector<Point> p;
-//	Point tempP;
-//
-//	for (int i = 0; i < x.size(); ++i) {
-//		tempP = {x[i],y[i]};
-//		p.push_back(tempP);
-//	};
-//
-//	std::sort(p.begin(), p.end(), sortPointXDimension);
-//
-//	ASSERT_EQ(p[0].x, -4);
-//	ASSERT_EQ(p[0].y, 0);
-//
-//	std::sort(p.begin(), p.end(), sortPointYDimension);
-//	ASSERT_EQ(p[0].y, -4);
-//	ASSERT_EQ(p[0].x, -3);
-//	ASSERT_EQ(p[10].y, 4);
-//	ASSERT_EQ(p[10].x, 4);
-//}
-//
-//TEST(PointDistance, Test1) {
-//	vector<int> x = { 0, 0 };
-//	vector<int> y = { 3, 4 };
-//
-//	float f = minimalDistance(x, y);
-//	ASSERT_FLOAT_EQ(f, 5);
-//}
-//
-//TEST(ClosestDistance, Test1) {
-//	vector<int> x = { 0, 3 };
-//	vector<int> y = { 0, 4 };
-//	float result = 5.0;
-//	ASSERT_FLOAT_EQ(result, minimalDistance(x, y));
-//}
-//
-//TEST(ClosestDistance, Test2) {
-//	vector<int> x = { 0, 3, 5 };
-//	vector<int> y = { 0, 4, 6 };
-//	float result = 2.828427;
-//	ASSERT_FLOAT_EQ(result, minimalDistance(x, y));
-//}
-//
-//TEST(ClosestDistance, Test3) {
-//	vector<int> x = { 7, 1, 4, 7 };
-//	vector<int> y = { 7, 100, 8, 7 };
-//	float result = 0.0;
-//	ASSERT_FLOAT_EQ(result, minimalDistance(x, y));
-//}
-//
-//TEST(ClosestDistance, Test4) {
-//	vector<int> x = { 4, -2, -3, -1, 2, -4, 1, -1, 3, -4, -2 };
-//	vector<int> y = { 4, -2, -4, 3, 3, 0, 1, -1, -1, 2, 4 };
-//	float result = 1.4142135;
-//	ASSERT_FLOAT_EQ(result, minimalDistance(x, y));
+//	ASSERT_EQ(2, getChange(2));
+//	ASSERT_EQ(9, getChange(34));
 //}
 
 int main() {
-  size_t n;
-  std::cin >> n;
-  vector<int> x(n);
-  vector<int> y(n);
-  for (size_t i = 0; i < n; i++) {
-    std::cin >> x[i] >> y[i];
-  }
-  std::cout << std::fixed;
-  std::cout << std::setprecision(9) << minimalDistance(x, y) << "\n";
+  int m;
+  std::cin >> m;
+  std::cout << getChange(m) << '\n';
 }