Dp problem help(Coin Combinations)

problem:https://cses.fi/problemset/task/1636/

My solution:
#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
ll arr[101],dp[101][1000001];
const ll p=pow(10,9)+7;

int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
ll n,s;
cin>>n>>s;
for(ll i=0;i<n;i++)
{
cin>>arr[i];
}
for(ll i=0;i<=n;i++)
{

	for(ll j=0;j<=s;j++)
	{
		if(j!=0 and i==0)
		{
			dp[i][j]=0;
		}
		if(j==0)
		{
			dp[i][j]=1;
		}
		else
		{
			break;
		}

	}
}
for(ll i=1;i<=n;i++)
{
	for(ll j=1;j<=s;j++)
	{

		if(j-arr[i-1]>=0)
		{
			dp[i][j]=(dp[i][j-arr[i-1]]%p+dp[i-1][j]%p)%p;
		}
		else
		{
			dp[i][j]=dp[i-1][j]%p;
		}
	}
}
cout<<dp[n][s];

}
it’s showing run time error for me in some of the cases
e.g
100 1000000
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 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
expected output:869167734

Didn’t you ask this before as well?
(Dp problem help(Coin Combinations))

And use ``` for formatting the code. :slight_smile:
For example,

#include <iostream>
using namespace std;

int main() {
	// your code goes here
	return 0;
}

This is how it looks when you use ```.

3 Likes

long long dp[ 101 ][ 1000001 ]

It allocates the memory from the stack. Stack memory is limited so you can’t do too big allocations.

Just change long long int into int , it will work fine , as values won’t exceed pow( 10 , 9 ) + 7
int will be fine.

But if you want to declare it as long long then do it dynamically.

long long **dp ;

dp = new ( long long* )[ 101 ] ;

for( int i = 0 ; i < 101 ; i++ )
         dp[ i ] = new long long[ 1000001 ] ;

It allocates the memory from the heap. Heap allocations can be big.

4 Likes

Thx dude

1 Like

My pleasure

i have one more problem…
https://cses.fi/problemset/task/1158/
My code:
#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;

const ll mod=pow(10,9)+7;

int main()
{

ll n,x;
ll price[1001],pages[1001];
ll **dp ;
dp = new long long* [ 1001 ] ;

for( int i = 0 ; i < 1001 ; i++ )
{
    dp[i]=new long long[ 1000001 ];
}
cin>>n>>x;
for(int i=0;i<n;i++)
{
	cin>>price[i];
}
for(int i=0;i<n;i++)
{
	cin>>pages[i];
}
for(ll i=0;i<=n;i++)
{
    for(ll j=0;j<=x;j++)
    {
        if(i==0 || j==0)
		{
			dp[i][j]=0;
		}
		else
		{
			break;
		}
    }
}
for(ll i=1;i<=n;i++)
{
	for(ll j=1;j<=x;j++)
	{

		if(j-price[i-1]>=0)
		{
			dp[i][j]=max(dp[i-1][j-price[i-1]]+pages[i-1],dp[i-1][j]);
		}
		else
		{
			dp[i][j]=dp[i-1][j];
		}
	}
}
cout<<dp[n][x];
return 0;

}

Again run time error!!
test case:
1000 99999
451 356 240 484 650 392 760 748 948 618 12 12 506 178 16 100 996 454 672 382 442 956 716 522 568 520 708 490 394 450 884 216 32 760 588 602 382 426 514 14 774 870 428 738 794 28 210 590 542 896 6 676 846 842 380 604 182 600 990 928 826 620 988 934 890 214 334 848 326 312 248 712 290 790 28 30 888 320 854 878 482 246 670 116 974 298 530 758 864 914 880 486 674 116 814 866 390 84 324 924 80 470 816 162 200 86 950 646 690 154 724 754 54 292 958 548 720 622 676 342 846 140 174 874 238 770 382 340 474 724 694 738 580 760 130 730 346 508 650 808 874 484 530 990 4 868 310 596 970 192 628 44 178 228 476 208 186 336 332 664 536 228 338 500 198 472 788 966 22 770 20 808 656 108 576 834 212 316 202 824 656 738 364 596 864 354 406 550 368 38 628 816 154 368 240 190 210 730 742 82 166 328 256 306 718 206 834 334 472 844 416 774 214 554 630 976 436 72 556 964 980 326 432 456 738 646 378 340 58 698 6 146 66 218 854 208 960 996 598 642 460 324 802 360 920 750 100 878 338 842 480 30 284 286 178 236 736 664 924 84 468 618 952 174 442 686 300 776 786 582 298 40 660 332 752 700 632 40 750 906 622 438 582 206 436 144 492 248 330 578 616 622 106 366 140 228 20 702 334 64 144 400 856 280 638 902 298 164 594 902 4 242 750 374 674 36 830 350 738 938 902 204 708 2 644 374 220 514 724 722 600 134 168 948 258 636 472 780 342 266 310 546 654 494 298 232 312 360 704 120 244 646 278 768 272 494 216 220 510 188 190 914 536 660 82 572 702 466 502 554 506 836 176 344 794 908 118 286 824 866 944 322 956 340 522 296 242 148 542 678 358 826 842 978 908 222 702 138 950 138 918 334 326 908 682 854 936 640 922 322 60 304 904 402 858 924 454 300 464 168 970 964 326 722 536 50 568 308 652 530 134 660 444 296 246 924 322 134 824 296 376 50 350 916 470 138 322 628 764 658 316 256 112 612 496 918 76 576 68 690 838 720 88 108 704 4 348 556 902 646 376 950 350 466 234 376 374 858 374 572 292 594 534 510 298 718 182 810 722 756 532 956 320 986 830 604 744 490 114 708 490 938 338 370 456 756 564 860 688 996 310 170 254 648 604 100 648 546 884 416 750 666 782 954 260 976 956 34 290 680 208 40 300 22 118 662 354 106 882 760 950 896 720 292 126 606 230 228 574 656 542 736 310 140 70 790 10 606 360 486 542 774 224 112 906 556 212 592 684 296 942 236 662 874 590 288 310 424 654 454 30 264 36 662 798 186 412 248 282 782 172 594 828 84 542 934 122 312 886 162 354 246 470 340 378 170 658 262 572 222 90 196 682 316 526 788 962 382 134 204 356 556 882 180 6 356 14 2 108 306 826 572 470 948 784 614 140 742 698 850 140 668 964 216 292 128 432 298 596 672 786 730 914 996 314 608 896 776 30 650 412 56 664 500 512 878 608 758 658 942 290 258 256 936 380 870 354 658 522 524 778 752 376 108 424 326 770 578 986 606 508 750 676 850 184 626 718 796 752 86 162 348 536 784 66 34 304 296 612 524 294 34 326 482 112 392 266 358 988 414 786 10 566 434 308 418 408 878 2 816 100 44 346 702 2 106 448 142 378 92 180 624 800 808 792 248 186 72 34 210 914 420 902 536 682 906 328 714 586 494 446 796 320 232 236 18 356 956 76 104 458 320 998 340 772 262 880 678 758 506 402 658 416 266 978 372 390 208 408 492 686 486 28 854 732 872 938 686 916 688 522 430 862 896 808 772 828 584 972 980 362 258 394 616 660 964 594 398 904 930 842 856 528 986 938 734 360 22 764 516 152 512 820 194 786 10 672 368 932 692 998 298 218 116 390 66 366 620 810 444 672 944 402 618 522 428 344 554 422 708 646 902 256 684 248 436 944 790 244 514 260 60 562 410 386 478 674 960 656 944 864 160 344 754 778 206 550 404 684 254 436 686 122 74 500 990 196 478 452 626 76 904 524 584 622 866 646 430 208 796 150 2 714 442 682 796 928 76 482 424 24 354 502 660 984 756 182 452 222 724 618 90 566 72 86 952 168 736 360 226 842 810 928 18 74 284 906 446 744 806 986 976 458 952 714 216 392 756 404 902 640 396 198 584 550 980 116 934 888 920 636 882 214 732 112 548 128 84 502 478 180 268 888 750 258 56 870 418 240 314 510 480 196 360 822 360 1000 128 452 628
451 356 240 484 650 392 760 748 948 618 12 12 506 178 16 100 996 454 672 382 442 956 716 522 568 520 708 490 394 450 884 216 32 760 588 602 382 426 514 14 774 870 428 738 794 28 210 590 542 896 6 676 846 842 380 604 182 600 990 928 826 620 988 934 890 214 334 848 326 312 248 712 290 790 28 30 888 320 854 878 482 246 670 116 974 298 530 758 864 914 880 486 674 116 814 866 390 84 324 924 80 470 816 162 200 86 950 646 690 154 724 754 54 292 958 548 720 622 676 342 846 140 174 874 238 770 382 340 474 724 694 738 580 760 130 730 346 508 650 808 874 484 530 990 4 868 310 596 970 192 628 44 178 228 476 208 186 336 332 664 536 228 338 500 198 472 788 966 22 770 20 808 656 108 576 834 212 316 202 824 656 738 364 596 864 354 406 550 368 38 628 816 154 368 240 190 210 730 742 82 166 328 256 306 718 206 834 334 472 844 416 774 214 554 630 976 436 72 556 964 980 326 432 456 738 646 378 340 58 698 6 146 66 218 854 208 960 996 598 642 460 324 802 360 920 750 100 878 338 842 480 30 284 286 178 236 736 664 924 84 468 618 952 174 442 686 300 776 786 582 298 40 660 332 752 700 632 40 750 906 622 438 582 206 436 144 492 248 330 578 616 622 106 366 140 228 20 702 334 64 144 400 856 280 638 902 298 164 594 902 4 242 750 374 674 36 830 350 738 938 902 204 708 2 644 374 220 514 724 722 600 134 168 948 258 636 472 780 342 266 310 546 654 494 298 232 312 360 704 120 244 646 278 768 272 494 216 220 510 188 190 914 536 660 82 572 702 466 502 554 506 836 176 344 794 908 118 286 824 866 944 322 956 340 522 296 242 148 542 678 358 826 842 978 908 222 702 138 950 138 918 334 326 908 682 854 936 640 922 322 60 304 904 402 858 924 454 300 464 168 970 964 326 722 536 50 568 308 652 530 134 660 444 296 246 924 322 134 824 296 376 50 350 916 470 138 322 628 764 658 316 256 112 612 496 918 76 576 68 690 838 720 88 108 704 4 348 556 902 646 376 950 350 466 234 376 374 858 374 572 292 594 534 510 298 718 182 810 722 756 532 956 320 986 830 604 744 490 114 708 490 938 338 370 456 756 564 860 688 996 310 170 254 648 604 100 648 546 884 416 750 666 782 954 260 976 956 34 290 680 208 40 300 22 118 662 354 106 882 760 950 896 720 292 126 606 230 228 574 656 542 736 310 140 70 790 10 606 360 486 542 774 224 112 906 556 212 592 684 296 942 236 662 874 590 288 310 424 654 454 30 264 36 662 798 186 412 248 282 782 172 594 828 84 542 934 122 312 886 162 354 246 470 340 378 170 658 262 572 222 90 196 682 316 526 788 962 382 134 204 356 556 882 180 6 356 14 2 108 306 826 572 470 948 784 614 140 742 698 850 140 668 964 216 292 128 432 298 596 672 786 730 914 996 314 608 896 776 30 650 412 56 664 500 512 878 608 758 658 942 290 258 256 936 380 870 354 658 522 524 778 752 376 108 424 326 770 578 986 606 508 750 676 850 184 626 718 796 752 86 162 348 536 784 66 34 304 296 612 524 294 34 326 482 112 392 266 358 988 414 786 10 566 434 308 418 408 878 2 816 100 44 346 702 2 106 448 142 378 92 180 624 800 808 792 248 186 72 34 210 914 420 902 536 682 906 328 714 586 494 446 796 320 232 236 18 356 956 76 104 458 320 998 340 772 262 880 678 758 506 402 658 416 266 978 372 390 208 408 492 686 486 28 854 732 872 938 686 916 688 522 430 862 896 808 772 828 584 972 980 362 258 394 616 660 964 594 398 904 930 842 856 528 986 938 734 360 22 764 516 152 512 820 194 786 10 672 368 932 692 998 298 218 116 390 66 366 620 810 444 672 944 402 618 522 428 344 554 422 708 646 902 256 684 248 436 944 790 244 514 260 60 562 410 386 478 674 960 656 944 864 160 344 754 778 206 550 404 684 254 436 686 122 74 500 990 196 478 452 626 76 904 524 584 622 866 646 430 208 796 150 2 714 442 682 796 928 76 482 424 24 354 502 660 984 756 182 452 222 724 618 90 566 72 86 952 168 736 360 226 842 810 928 18 74 284 906 446 744 806 986 976 458 952 714 216 392 756 404 902 640 396 198 584 550 980 116 934 888 920 636 882 214 732 112 548 128 84 502 478 180 268 888 750 258 56 870 418 240 314 510 480 196 360 822 360 1000 128 452 628

Op:99999
It’s running fine on Online compiler ,but moment i submit it in cses ,it shows me runtime error in some of the cases.
I found some other guy’s code from codefroces,actually i was not trying to copy but i just wanted to figure out what the hell is wrong in my code as it works on online compiler,i have tried this to debug since 2 hrs and there is no +ve result .
If someone could figure me out i really thank you sir.

code of codeforces guy:

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, x;
  cin >> n >> x;
  vector<int> price(n), pages(n);
  for (int&v : price) cin >> v;
  for (int&v : pages) cin >> v;
  vector<vector<int>> dp(n+1,vector<int>(x+1,0));
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= x; j++) {
      dp[i][j] = dp[i-1][j];
      int left = j-price[i-1];
      if (left >= 0) {
	dp[i][j] = max(dp[i][j], dp[i-1][left]+pages[i-1]);
      }
    }
  }
  cout << dp[n][x] << endl;
}