Tag Archives: Leetcode 357

Leetcode 357: How to calculate the number of digits with different digits

Such a simple thing, mentality exploded, the first glance will know very simple, originally intended to do half an hour, the results tamper tamper and nearly 50 minutes, but also in the middle of debugging several times, the algorithm is not really can’t.
AC after the state of mind and exploded, this know this is a digit dp, but I use greed (turns out not greedy), thought for a long time also did not think of how to do with dp, in the burst of time, the original dp is to store the value of one place, ten place just

int countNumbersWithUniqueDigits(int n) {
	if(0==n)
		return 1;
	if(n<0 || n>10)
		return 0;
	int ret = 0;
	for(int i=n;i>=1;--i)
	{
		int ret1 = 1;
		int num = 9;
		for(int j=0;j<i;++j)
		{
			ret1 *= num;
			num = 0==j ?num : num-1;
		}
		ret += ret1;
	}
	return ret+1;
}