演算法訓練營
- 空間復雜度，fib理解，剪枝重復計算
- 核心考點：場景轉化模型，模型提取解法，簡單dp，fib
- 核心考點：場景轉化成模型，特殊情況分析，簡單dp
空間復雜度，fib理解，剪枝重復計算
遞回的方法我們已經很熟悉了，這里我們寫一個迭代版本的，
class Solution {
public:
int Fibonacci(int n) {
if (0 == n)
{
return n;
}
int first = 1;
int second = 1;
int third = 1;
while (n>2){
third = first + second;
first = second;
second = third;
n--;
}
return third;
}
};
核心考點：場景轉化模型，模型提取解法，簡單dp，fib
解題思路：
1.定義方程 f(n):青蛙跳上第n階臺階的總跳法數
2.轉移方程 f(n)=f（n-1）+f(n-2)
3.設定初始值f(0) f(1) f(2)
使用動態規劃的演算法：
class Solution {
public:
int jumpFloor(int number) {
int *dp = new int[number + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i < number; i++){
dp[i] = dp[i - 1] + dp[i - 2];
}
int num = dp[number];
delete dp;
return num;
}
};
核心考點：場景轉化成模型，特殊情況分析，簡單dp
理解：
用n個21的小矩形無重疊地覆寫一個2n的大矩形，每次放置的時候，無非兩種放法，橫著放或豎著放其中，橫著放一個之后，下一個的放法也就確定了，故雖然放置了兩個矩形，但屬于同一種放法，豎著放一個之后，本輪放置也就完成了，也屬于一種方法，
解題思路：
狀態定義：f(n) : 用n個21的小矩形無重疊地覆寫一個2n的大矩形所用的總方法數
轉移方程：f(n) = f(n-1)【最后一個豎著放】 + f(n-2)【最后兩個橫著放】
初始化：f(1) = 1,f(2) = 2,f(0)=1
class Solution {
public:
int rectCover(int number) {
int *dp = new int[number + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= number; i++)
{
dp[i] = dp[i - 1] + dp[i - 2];
}
int result = dp[number];
delete dp;
return result;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/298416.html
標籤：其他