動態規劃框架
動態規劃：Dynamic Programming
動態規劃問題的一般形式就是求最值 -> 窮舉
動態規劃的窮舉特點在于這類問題存在重疊子問題，如果暴力窮舉，效率極其低下，所以一般通過備忘錄或者DP table用空間來優化窮舉的程序，避免不必要的計算，
動態規劃三要素：重疊子問題、最優子結構、狀態轉移方程
重疊子問題：
最優子結構：
狀態轉移方程：窮舉的方式
思維框架：
明確base case -> 明確[狀態] -> 明確[選擇] -> 定義dp陣列、函式的含義
代碼框架：
# 初始化 base case
dp[0][0][...] = base
# 進行狀態轉移
for 狀態1 in 狀態1的所有取值：
for 狀態2 in 狀態2的所有取值：
for ...
dp[狀態1][狀態2][...] = 求最值(選擇1，選擇2...)
下面以例子方式詳解動態規劃的基本原理
斐波那契數列問題
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：
輸入：2
輸出：1
解釋：F(2) = F(1) + F(0) = 1 + 0 = 1.
示例 2：
輸入：3
輸出：2
解釋：F(3) = F(2) + F(1) = 1 + 1 = 2.
示例 3：
輸入：4
輸出：3
解釋：F(4) = F(3) + F(2) = 2 + 1 = 3.
提示：
0 ≤ N ≤ 30
由題意可以推到出一下遞推公式：
方法一：暴力遞回
//方法一：遞回
int fib(int n)
{
// base case
if (n == 0 || n == 1)
{
return 1;
}
return fib(n - 1) + fib(n - 2);
}
方法二：遞回 + 備忘錄(自頂向下)
//方法二：遞回 + 備忘錄（自頂向下）
int helper(int *rec_table, int n)
{
if (n == 0 || n == 1)
{
return n;
}
if (rec_table[n] != 0)
{
return rec_table[n];
}
rec_table[n] = helper(rec_table, n - 1) + helper(rec_table, n - 2);
return rec_table[n];
}
int fib(int n)
{
if (n == 0 || n == 1)
{
return n;
}
int *rec_table = (int *)malloc((n + 1) * sizeof(int));
memset(rec_table, 0, (n + 1) * sizeof(int));
rec_table[0] = 0;
rec_table[1] = 1;
return helper(rec_table, n);
}
方法三：動態規劃 + dp陣列
// 方法三：動態規劃，陣列/滾動變數
int fib(int n)
{
if (n == 0 || n == 1)
{
return n;
}
int *dp = (int *)malloc((n + 1) * sizeof(int));
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++)
{
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/198451.html
標籤：C
上一篇：題解——二叉樹哈夫曼編碼的實作