ones(nyoj 708)

題目：點選打開連結

好像出去玩啊啊啊啊啊……………………………………………………

這道題是不是我做得推得比較順的一個動歸題，雖然這題挺簡單的………………

題目輸入一個數n，這個數隻能用1，加号，乘号來組成且1不能連續出現，輸出n包含的1的個數的最小值。

dp[i]代表數字i包含1的最少個數，我将dp[i]都出事化為i， dp[i] = min (dp[i - 1] + 1, dp[i / j] + dp[j])，其中j是比i小且能j能整除i的數。

剛開始沒有想到dp[i - 1] + 1這個地方…………

#include <stdio.h>

int dp[10010];

int min (int a,  int b)
{
	return a < b ? a : b;
}

int main (void)
{
	int i, j;
	for(i = 0; i < 10010; i++)
		dp[i] = i;
	for(i = 6; i < 10010; i++)
	{
		for(j = 2; j < i; j++)
		{
			if(i % j == 0)
				dp[i] = min (dp[i], dp[i / j] + dp[j]);
		}
		dp[i] = min(dp[i], dp[i - 1] + 1);//第一次沒有寫這句WA了 
	}	
	int n;
	while(scanf("%d", &n) != EOF)
	{
		printf("%d\n", dp[n]);	
	}
	return 0;
}