Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Sign up
Appearance settings

Commit b0c3529

Browse files
DP questions with both Recursion and DP
1 parent fabeb53 commit b0c3529

File tree

4 files changed

+487
-0
lines changed

4 files changed

+487
-0
lines changed

‎Dynamic Programming/Coins Problem.ipynb

Lines changed: 139 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,139 @@
1+
{
2+
"cells": [
3+
{
4+
"cell_type": "markdown",
5+
"metadata": {},
6+
"source": [
7+
"## Coins Problem"
8+
]
9+
},
10+
{
11+
"cell_type": "code",
12+
"execution_count": 2,
13+
"metadata": {},
14+
"outputs": [],
15+
"source": [
16+
"import sys"
17+
]
18+
},
19+
{
20+
"cell_type": "code",
21+
"execution_count": 3,
22+
"metadata": {},
23+
"outputs": [],
24+
"source": [
25+
"INT_MAX=sys.maxsize\n",
26+
"INT_MIN=-sys.maxsize-1"
27+
]
28+
},
29+
{
30+
"cell_type": "markdown",
31+
"metadata": {},
32+
"source": [
33+
"## Solution of coins problem using Recursion"
34+
]
35+
},
36+
{
37+
"cell_type": "code",
38+
"execution_count": 11,
39+
"metadata": {},
40+
"outputs": [
41+
{
42+
"name": "stdout",
43+
"output_type": "stream",
44+
"text": [
45+
"4\n"
46+
]
47+
}
48+
],
49+
"source": [
50+
"def FindMinCoins(c,n,amt):\n",
51+
" if amt==0:\n",
52+
" return 0\n",
53+
" if amt<0:\n",
54+
" return INT_MAX\n",
55+
" coins = INT_MAX\n",
56+
" for i in range(0,n):\n",
57+
" res = FindMinCoins(c,n,amt-c[i])\n",
58+
" if res!=INT_MAX:\n",
59+
" coins = min(coins,res+1)\n",
60+
" return coins\n",
61+
"\n",
62+
"if __name__==\"__main__\":\n",
63+
" c = [1,2,3,4]\n",
64+
" n = len(c)\n",
65+
" amt = 15\n",
66+
" print(FindMinCoins(c,n,amt))"
67+
]
68+
},
69+
{
70+
"cell_type": "markdown",
71+
"metadata": {},
72+
"source": [
73+
"## Solution of coins problem using Dynamic Programming"
74+
]
75+
},
76+
{
77+
"cell_type": "code",
78+
"execution_count": 6,
79+
"metadata": {},
80+
"outputs": [
81+
{
82+
"name": "stdout",
83+
"output_type": "stream",
84+
"text": [
85+
"4\n"
86+
]
87+
}
88+
],
89+
"source": [
90+
"def FindMinCoins(c,n,amt):\n",
91+
" T = [None]*(amt+1)\n",
92+
" T[0] = 0\n",
93+
" for i in range(1,amt+1):\n",
94+
" T[i] = INT_MAX\n",
95+
" res = INT_MAX\n",
96+
" for j in range(0,n):\n",
97+
" if (i-c[j])>=0:\n",
98+
" res = T[i-c[j]]\n",
99+
" if res!=INT_MAX:\n",
100+
" T[i] = min(T[i],res+1)\n",
101+
" return T[amt]\n",
102+
"\n",
103+
"if __name__==\"__main__\":\n",
104+
" c = [1,2,3,4]\n",
105+
" n = len(c)\n",
106+
" amt = 15\n",
107+
" print(FindMinCoins(c,n,amt))"
108+
]
109+
},
110+
{
111+
"cell_type": "code",
112+
"execution_count": null,
113+
"metadata": {},
114+
"outputs": [],
115+
"source": []
116+
}
117+
],
118+
"metadata": {
119+
"kernelspec": {
120+
"display_name": "Python 3",
121+
"language": "python",
122+
"name": "python3"
123+
},
124+
"language_info": {
125+
"codemirror_mode": {
126+
"name": "ipython",
127+
"version": 3
128+
},
129+
"file_extension": ".py",
130+
"mimetype": "text/x-python",
131+
"name": "python",
132+
"nbconvert_exporter": "python",
133+
"pygments_lexer": "ipython3",
134+
"version": "3.7.6"
135+
}
136+
},
137+
"nbformat": 4,
138+
"nbformat_minor": 2
139+
}
Lines changed: 106 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,106 @@
1+
{
2+
"cells": [
3+
{
4+
"cell_type": "markdown",
5+
"metadata": {},
6+
"source": [
7+
"## Rod Cutting Problem - Obtain Maximum Profit - Recursion"
8+
]
9+
},
10+
{
11+
"cell_type": "code",
12+
"execution_count": 2,
13+
"metadata": {},
14+
"outputs": [
15+
{
16+
"name": "stdout",
17+
"output_type": "stream",
18+
"text": [
19+
"Maximum Obtainable Value is 10\n"
20+
]
21+
}
22+
],
23+
"source": [
24+
"import sys\n",
25+
"INT_MIN = -sys.maxsize-1\n",
26+
"def RodCut(price, n):\n",
27+
" if n==0:\n",
28+
" return 0\n",
29+
" maxvalue = INT_MIN\n",
30+
" for i in range(1,n+1):\n",
31+
" maxvalue = max(maxvalue,price[i-1]+RodCut(price,n-i))\n",
32+
" return maxvalue\n",
33+
"\n",
34+
"if __name__==\"__main__\":\n",
35+
" length = [1,2,3,4,5,6,7,8] \n",
36+
" price = [1,5,8,9,10,17,17,20]\n",
37+
" size = len(length) \n",
38+
" print(\"Maximum Obtainable Value is \" + str(RodCut(price, 4))) "
39+
]
40+
},
41+
{
42+
"cell_type": "markdown",
43+
"metadata": {},
44+
"source": [
45+
"## Rod cut problem solution - Dynamic Programming"
46+
]
47+
},
48+
{
49+
"cell_type": "code",
50+
"execution_count": 7,
51+
"metadata": {},
52+
"outputs": [
53+
{
54+
"name": "stdout",
55+
"output_type": "stream",
56+
"text": [
57+
"Maximum Obtainable Value is 13\n"
58+
]
59+
}
60+
],
61+
"source": [
62+
"def Rod_Cut(price, n): \n",
63+
" T = [0]*(n+1)\n",
64+
" T[0] = 0\n",
65+
" for i in range(1, n+1): \n",
66+
" for j in range(i): \n",
67+
" T[i] = max(T[i], price[j] + T[i-j-1]) \n",
68+
" return T[n] \n",
69+
"\n",
70+
"if __name__==\"__main__\":\n",
71+
" length = [1,2,3,4,5,6,7,8] \n",
72+
" price = [1,5,8,9,10,17,17,20]\n",
73+
" size = len(length) \n",
74+
" print(\"Maximum Obtainable Value is \" + str(Rod_Cut(price, 5))) "
75+
]
76+
},
77+
{
78+
"cell_type": "code",
79+
"execution_count": null,
80+
"metadata": {},
81+
"outputs": [],
82+
"source": []
83+
}
84+
],
85+
"metadata": {
86+
"kernelspec": {
87+
"display_name": "Python 3",
88+
"language": "python",
89+
"name": "python3"
90+
},
91+
"language_info": {
92+
"codemirror_mode": {
93+
"name": "ipython",
94+
"version": 3
95+
},
96+
"file_extension": ".py",
97+
"mimetype": "text/x-python",
98+
"name": "python",
99+
"nbconvert_exporter": "python",
100+
"pygments_lexer": "ipython3",
101+
"version": "3.7.6"
102+
}
103+
},
104+
"nbformat": 4,
105+
"nbformat_minor": 4
106+
}
Lines changed: 122 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,122 @@
1+
{
2+
"cells": [
3+
{
4+
"cell_type": "markdown",
5+
"metadata": {},
6+
"source": [
7+
"## Dynamic Programming"
8+
]
9+
},
10+
{
11+
"cell_type": "markdown",
12+
"metadata": {},
13+
"source": [
14+
"Fibonacci Series's Nth term\n",
15+
"series:\n",
16+
"0,1,1,2,3,5,8,13,21,34,55,89,.................. nth"
17+
]
18+
},
19+
{
20+
"cell_type": "markdown",
21+
"metadata": {},
22+
"source": [
23+
"## Solution using Recursion"
24+
]
25+
},
26+
{
27+
"cell_type": "code",
28+
"execution_count": 6,
29+
"metadata": {},
30+
"outputs": [
31+
{
32+
"name": "stdout",
33+
"output_type": "stream",
34+
"text": [
35+
"nth term of fibonacci series = 34\n"
36+
]
37+
}
38+
],
39+
"source": [
40+
"def fib(n):\n",
41+
" if n==1:\n",
42+
" return 0\n",
43+
" if n==2:\n",
44+
" return 1;\n",
45+
" return fib(n-1)+fib(n-2)\n",
46+
"\n",
47+
"if __name__==\"__main__\":\n",
48+
" print(\"nth term of fibonacci series = %d\"%fib(10))"
49+
]
50+
},
51+
{
52+
"cell_type": "markdown",
53+
"metadata": {},
54+
"source": [
55+
"### Memorization (Dynamic programming Approch)"
56+
]
57+
},
58+
{
59+
"cell_type": "code",
60+
"execution_count": 22,
61+
"metadata": {},
62+
"outputs": [
63+
{
64+
"name": "stdout",
65+
"output_type": "stream",
66+
"text": [
67+
"nth term of fibonacci series=34\n"
68+
]
69+
}
70+
],
71+
"source": [
72+
"#Main target is to store the past data\n",
73+
"def fib(n):\n",
74+
" a = 0\n",
75+
" b = 1\n",
76+
" if n < 0: \n",
77+
" print(\"Incorrect input\") \n",
78+
" elif n == 0: \n",
79+
" return a \n",
80+
" elif n == 1: \n",
81+
" return b \n",
82+
" else: \n",
83+
" for i in range(2,n): \n",
84+
" c = a + b \n",
85+
" a = b \n",
86+
" b = c \n",
87+
" return b \n",
88+
"\n",
89+
"if __name__==\"__main__\":\n",
90+
" print(\"nth term of fibonacci series=%d\"%fib(10))"
91+
]
92+
},
93+
{
94+
"cell_type": "code",
95+
"execution_count": null,
96+
"metadata": {},
97+
"outputs": [],
98+
"source": []
99+
}
100+
],
101+
"metadata": {
102+
"kernelspec": {
103+
"display_name": "Python 3",
104+
"language": "python",
105+
"name": "python3"
106+
},
107+
"language_info": {
108+
"codemirror_mode": {
109+
"name": "ipython",
110+
"version": 3
111+
},
112+
"file_extension": ".py",
113+
"mimetype": "text/x-python",
114+
"name": "python",
115+
"nbconvert_exporter": "python",
116+
"pygments_lexer": "ipython3",
117+
"version": "3.7.6"
118+
}
119+
},
120+
"nbformat": 4,
121+
"nbformat_minor": 2
122+
}

0 commit comments

Comments
(0)

AltStyle によって変換されたページ (->オリジナル) /