LeetCode Day동적 프로그래밍 Part1
- 王林원래의
- 2024-07-18 12:46:25771검색
509. 피보나치 수
일반적으로 F(n)으로 표시되는 피보나치 수열은 피보나치 수열이라고 하는 수열을 형성하며, 각 수는 0과 1부터 시작하여 앞의 두 수의 합이 됩니다. 즉,
F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), n > 1.
n이 주어지면 F(n)을 계산합니다.
예 1:
입력: n = 2
출력: 1
설명: F(2) = F(1) + F(0) = 1 + 0 = 1.
예시 2:
입력: n = 3
출력: 2
설명: F(3) = F(2) + F(1) = 1 + 1 = 2.
예시 3:
입력: n = 4
출력: 3
설명: F(4) = F(3) + F(2) = 2 + 1 = 3.
제약사항:
0 원본페이지
재귀 방법
public int fib(int n) {
if(n==0){
return 0;
}
else if(n==1){
return 1;
}
else{
return fib(n-1) + fib(n-2);
}
}
재귀 방법은 DFS와 유사하게 깊이 들어간 다음 역추적을 수행하여 최종 답을 얻습니다.
시간: O(2^n)
공간: O(1)
private int[] dp = new int[31];
public int fib(int n) {
if(n<2){
dp[n] = n;
return n;
}
if(n>=2 && dp[n]!=0){
return dp[n];
}
dp[n] = fib(n-1) + fib(n-2);
return dp[n];
}
동일한 요소의 재발을 방지하기 위해 전역 배열을 사용하여 결과를 저장할 수 있습니다. 예를 들어 아래 그림은 f(17)과 f(18)이 두 개의 서로 다른 재귀 경로이고 일반적인 재귀 방법을 사용하는 경우 두 번 이상 계산해야 함을 보여줍니다.
시간: O(n), 공간: O(n)
동적 프로그래밍
public int fib(int n) {
if(n<2){
return n;
}
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
for(int i=2; i<=n; i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
재귀는 위에서 아래로 작동한 다음 역추적되며, 메모리 재귀는 이중 계산을 피하기 위해 재귀 결과를 저장합니다. 이제 동적 프로그래밍은 아래에서 위로 작동하며 각 단계의 결과를 dp 배열에 저장합니다.
시간: O(n)
공백: O(n)
또한 배열 대신 제한 숫자를 동적으로 업데이트할 수 있습니다. 이렇게 하면 특히 수많은 요소의 경우 공간 복잡성이 줄어듭니다.
public int fib(int n) {
if(n<2){
return n;
}
int start = 0;
int pre = 1;
int res = pre;
for(int i=2; i<=n; i++){
res = start + pre;
start = pre;
pre = res;
}
return res;
}
70. 계단 오르기
당신은 계단을 오르고 있습니다. 정상에 도달하려면 n 단계가 필요합니다.
때마다 1~2계단씩 오를 수 있습니다. 얼마나 많은 방법으로 정상에 오를 수 있나요?
예 1:
입력: n = 2
출력: 2
설명: 정상에 오르는 방법은 두 가지가 있습니다.
- 1단계 + 1단계
- 2단계 예시 2:
입력: n = 3
출력: 3
설명: 정상에 오르는 방법은 세 가지가 있습니다.
- 1단계 + 1단계 + 1단계
- 1단계 + 2단계
- 2단계 + 1단계
70. 계단 오르기
당신은 계단을 오르고 있습니다. 정상에 도달하려면 n 단계가 필요합니다.
때마다 1~2계단씩 오를 수 있습니다. 얼마나 많은 방법으로 정상에 오를 수 있나요?
예 1:
입력: n = 2
출력: 2
설명: 정상에 오르는 방법은 두 가지가 있습니다.
- 1단계 + 1단계
- 2단계 예시 2:
입력: n = 3
출력: 3
설명: 정상에 오르는 방법은 세 가지가 있습니다.
- 1단계 + 1단계 + 1단계
- 1단계 + 2단계
- 2단계 + 1단계
제약사항:
1 원본페이지
public int climbStairs(int n) {
if(n<3){
return n;
}
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
for(int i=3; i<=n; i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
public int climbStairs(int n) {
if(n<3){
return n;
}
int prepre = 1;
int pre = 2;
int res = 0;
for(int i=3; i<=n; i++){
res = prepre + pre;
prepre = pre;
pre = res;
}
return res;
}
746. 계단 오르기의 최소 비용
cost[i]가 계단의 i번째 계단의 비용인 정수 배열 비용이 주어졌습니다. 비용을 지불하고 나면 한 계단, 두 계단 올라갈 수 있습니다.
인덱스가 0인 단계부터 시작하거나 인덱스가 1인 단계부터 시작할 수 있습니다.
최상층에 도달하기 위한 최소 비용을 반환합니다.
예 1:
입력: 비용 = [10,15,20]
출력: 15
설명: 인덱스 1에서 시작합니다.
- 15달러를 지불하고 두 계단을 올라 정상에 도달하세요. 총 비용은 15입니다. 예시 2:
입력: 비용 = [1,100,1,1,1,100,1,1,100,1]
출력: 6
설명: 인덱스 0에서 시작합니다.
- 1을 지불하고 두 계단을 올라가면 지수 2에 도달합니다.
- 1을 지불하고 두 계단을 올라가면 지수 4에 도달합니다.
- 1을 지불하고 두 계단을 올라가면 지수 6이 됩니다.
- 1을 지불하고 한 단계 올라가면 지수 7이 됩니다.
- 1을 지불하고 두 계단을 올라가면 지수 9에 도달합니다.
- 1달러를 지불하고 한 계단만 올라가면 정상에 도달할 수 있습니다. 총 비용은 6입니다.
제약사항:
2
0
원본페이지
public int minCostClimbingStairs(int[] cost) {
if(cost.length < 2){
return 0;
}
int[] dp = new int[cost.length+1];
dp[0] = 0;
dp[1] = 0;
for(int i=2; i<dp.length; i++){
dp[i] = Math.min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);
}
return dp[dp.length-1];
}
the key thing of this problem is the `init array` and `the meaning of the array` and the `Recurrence relation`
질문에서 인덱스 0과 인덱스 1에서 시작할 수 있다는 점을 주의하세요. 이는 계단 수가 2보다 작으면 해당 지점에서 시작할 수 있고 시작 동작이 변경되기 때문에 비용이 0이 된다는 것을 의미합니다. 비용 0, 이동 비용의 동작만 수행됩니다.
위 내용은 LeetCode Day동적 프로그래밍 Part1의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!