Problem in my dp code


#1


https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=3654

it brings a wrong answer

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
bool notprime[1121];
int dp[1125]/*rem*/[1120]/*ind*/;
vector<int>primes;
int n;
void SieveOfEratosthenes(int n=1120)
{
	for (int p = 2; p*p <= n; p++)
		if (notprime[p] == false)
		{
			primes.push_back(p);
			for (int i = p * 2; i <= n; i += p)
				notprime[i] = true;
		}
}
int solve(int rem, int ind, int no)
{
	if (rem == 0)return 1;
	if (no == n||ind==primes.size()||rem<0)return 0;
	if (dp[rem][ind] != -1)return dp[rem][ind];
	return dp[rem][ind]=solve(rem-primes[ind],ind,no+1) + solve(rem,ind+1,no);
}
int main()
{
	int x;
	SieveOfEratosthenes();
	memset(dp, -1, sizeof dp);
	cin >> x >> n;
	while (x != 0 || n != 0)
	{
		cout<<solve(x, 0, 0)<<endl;
		cin >> x >> n;
	}
	return 0;
}


#2

I think you should comment out the dp until you've got the algorithm itself right. (1 bug here)
You aren't generating enough primes. (1 bug)
You can investigate which solutions it's finding, for small input values it'll be easy to verify. (2 bugs here)

Got the right idea though.

Comments and good names can help you reason about your code. If you write comments that describe what something is supposed to be doing, then you can compare the code to the comment separately from all the other code. You can also reason about whether what the comments describe amount to a correct solution.
Competetive programming isn't a beauty contest, but until you've mastered what you're doing I don't think you should be taking shortcuts that hurt your ability to reason about your code.
I can't keep very much in my head at once while writing code, so I convince myself of that doing certain steps will have the desired result, and then focus on implementing each individual step correctly in isolation from each other. Sometimes that means splitting steps up into smaller steps as well, whatever it takes to be able to reason about each thing as a whole without straining myself too much.


#3

thank you very much for your help i have fixed the errors you told me and
it worked in a right way.also thanks for your advices i will take them into
consideration.


#4

This topic was automatically closed 7 days after the last reply. New replies are no longer allowed.