DP

[LeetCode] 139. Word Break

139. Word Break Medium Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. Note that the same word in the dictionary may be reused multiple times in the segmentation. Example 1: Input: s = "leetcode", wordDict = ["leet","code"] Output: true Explanation: Return true because "leetcode" can be segm..

[LeetCode - Didi labs 기출문제] 265. Paint House II

265. Paint House II Hard There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color. The cost of painting each house with a certain color is represented by an n x k cost matrix costs. For example, costs[0][0] is the cost of..

1003 번 문제 피보나치 함수 Dynamic Programming

DP를 공부하는데 처음 해보면 괜찮을 문제같다. 동전 문제를 바로 해보는 건 조금 어려운것 같기도 하고, 아무튼 0을 호출했을때 0을 출력 1을 호출했을때 1을 출력.이것을 계속 단계 별로 저장해 나아가면서, 최상단의 호출한 번호에서 몇번을 출력해 주었는지 알아내면 된다. DP 배열 0 1 2 3 4 5 6 7 8 9 1/0 0/1 1/1 1/2 2/3 3/5 5/8 . . . dp[0] = 1/0; dp[1] = 0/1;2는 0과 1을 더한 것이고, 3은 2와 1의 결과 값을 더한 것이다. 즉 앞에서 부터, 차례대로 결과값을 쌓아가면 된다. 소스 보기 #include int main(){ int dp[41][2]={0}; int n=0,t=0; scanf("%d",&n); dp[0][0]=1; dp[0..

2163 초콜릿 자르기 Dynamic Programing 백준

2163 초콜릿 자르기 Dynamic Programinghttps://www.acmicpc.net/problem/2163백준 온라인 저지 C++ 배우기 (1~50)문제집을 풀면서 조금 생각해야되는 문제라고 생각하여 글을 쓴다. Dynamic Programing 동적 프로그래밍을 이용하여 풀었다.초콜릿을 쪼갤때마다, 쪼갠 크기에서 1X1 초콜릿이 될때까지의 횟수를 2차원 배열에 저장 했다.1X1 이면 0이며, 가로로 인덱스가 1씩 증가할때마다 1씩 증가 시켜준다. 그 외의 초콜릿은 그 열의 초콜릿 갯수만큼 더 해주면 된다.2X2 는 1X2 에서 2를 더 해주면 총 3번 쪼갠값 ! 아이 몰라 소스코드는 아래에 ! #include using namespace std;int main(){ int cho[301]..