dp table
I want to create a DP table
Dp table should look like this
https://dlmf.nist.gov/26.9#E1
Please help
1
2
3
4
5
6
7
8
9
10
|
sudo code goes like this
f(n,k):
if(n==k)
return 1;
if(n==0)
return 0;
if(dp[n][k]!=-1)
return dp[n][k];
b=f(n-k,k)+f(n-1,k-1);
return dp[n][k]=b;
|
Your pseudocode is wrong.
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
|
#include <iostream>
#include <iomanip>
#include <string>
using namespace std;
const int NMAX = 10, KMAX = 10;
int p[1+NMAX][1+KMAX];
const int WIDTH = 2;
//==========================================================
void setArray()
{
for ( int k = 0; k <= KMAX; k++ ) p[0][k] = 1;
for ( int n = 1; n <= NMAX; n++ )
{
p[n][0] = 0;
for ( int k = 1; k <= KMAX; k++ )
{
p[n][k] = p[n][k-1];
if ( k <= n ) p[n][k] += p[n-k][k];
}
}
}
//==========================================================
void drawArray()
{
#define FMT << ' ' << setw( WIDTH ) <<
cout FMT ' ' << " |";
for ( int k = 0; k <= KMAX; k++ ) cout FMT k;
cout << '\n';
cout << string( ( 1 + KMAX ) * ( WIDTH + 1 ) + WIDTH + 3, '-' ) << '\n';
for ( int n = 0; n <= NMAX; n++ )
{
cout FMT n << " |";
for ( int k = 0; k <= KMAX; k++ ) cout FMT p[n][k];
cout << '\n';
}
}
//==========================================================
int main()
{
setArray();
drawArray();
}
|
| 0 1 2 3 4 5 6 7 8 9 10
--------------------------------------
0 | 1 1 1 1 1 1 1 1 1 1 1
1 | 0 1 1 1 1 1 1 1 1 1 1
2 | 0 1 2 2 2 2 2 2 2 2 2
3 | 0 1 2 3 3 3 3 3 3 3 3
4 | 0 1 3 4 5 5 5 5 5 5 5
5 | 0 1 3 5 6 7 7 7 7 7 7
6 | 0 1 4 7 9 10 11 11 11 11 11
7 | 0 1 4 8 11 13 14 15 15 15 15
8 | 0 1 5 10 15 18 20 21 22 22 22
9 | 0 1 5 12 18 23 26 28 29 30 30
10 | 0 1 6 14 23 30 35 38 40 41 42 |
Last edited on
If you insist on doing it by memoisation it would look something like this (and your pseudocode is still wrong):
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
|
#include <iostream>
#include <iomanip>
#include <string>
using namespace std;
const int NMAX = 10, KMAX = 10;
int p[1+NMAX][1+KMAX];
const int WIDTH = 2;
//==========================================================
int f( int n, int k )
{
if ( p[n][k] == -1)
{
if ( n == 0 ) p[n][k] = 1;
else if ( k == 0 ) p[n][k] = 0;
else p[n][k] = f( n, k-1 ) + ( k <= n ? f( n-k, k ) : 0 );
}
return p[n][k];
}
//==========================================================
void drawArray()
{
#define FMT << ' ' << setw( WIDTH ) <<
cout FMT ' ' << " |";
for ( int k = 0; k <= KMAX; k++ ) cout FMT k;
cout << '\n';
cout << string( ( 1 + KMAX ) * ( WIDTH + 1 ) + WIDTH + 3, '-' ) << '\n';
for ( int n = 0; n <= NMAX; n++ )
{
cout FMT n << " |";
for ( int k = 0; k <= KMAX; k++ ) cout FMT f( n, k );
cout << '\n';
}
}
//==========================================================
int main()
{
for ( int nk = 0; nk < ( 1 + KMAX ) * ( 1 + NMAX ); nk++ ) *(p[0] + nk) = -1;
drawArray();
}
|
| 0 1 2 3 4 5 6 7 8 9 10
--------------------------------------
0 | 1 1 1 1 1 1 1 1 1 1 1
1 | 0 1 1 1 1 1 1 1 1 1 1
2 | 0 1 2 2 2 2 2 2 2 2 2
3 | 0 1 2 3 3 3 3 3 3 3 3
4 | 0 1 3 4 5 5 5 5 5 5 5
5 | 0 1 3 5 6 7 7 7 7 7 7
6 | 0 1 4 7 9 10 11 11 11 11 11
7 | 0 1 4 8 11 13 14 15 15 15 15
8 | 0 1 5 10 15 18 20 21 22 22 22
9 | 0 1 5 12 18 23 26 28 29 30 30
10 | 0 1 6 14 23 30 35 38 40 41 42 |
Topic archived. No new replies allowed.