Dynamic programming의 정석! 피보나치 수열을 dynamic programming로 구현 해 보았다.
사실 dp를 사용하지 않고 재귀로만 구현했더니 시간초과가 떠버렸다.
점화식은 f[n]=f[n-1]+f[n-2] 이다.
알고리즘 스터디를 계기로 Dynamic programming 문제를여러가지 접해보았는데 어렵게 느껴져서 백준 알고리즘에서 쉬운 dp문제부터 차근차근 올라가려 한다.
다음에 올릴 땐 자바 연습할 겸 자바로 올려야지!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | #include <stdio.h> #include <memory.h> int dp[500]; int fibonacci(int n) { if(dp[n]!=-1) return dp[n]; if (n==1||n==2) { return 1; } else { dp[n] = fibonacci(n-1) + fibonacci(n-2); } return dp[n]; } int main(void) { int x; memset(dp,-1,500); scanf("%d",&x); printf("%d",fibonacci(x)); return 0; } | cs |
'알고리즘 > dynamic programming' 카테고리의 다른 글
백준알고리즘 이항계수 (0) | 2017.03.26 |
---|