复习到k阶fibonacci数的时候，老师讲这是比较难的，然而不就是dp优化吗。
通过化简合并式子减少时间复杂度。
通过对前面无用的状态的覆盖来减少空间复杂度。(若要查询任意小于等于m的k阶fibonacci数这样的覆盖是不行的，必须全部记录下来。同01背包的一维的滚动数组。)
顺便复习一下模板计数dp.
题目
k阶斐波那契数列
题意
- 若m\(\gt\)k-1, \(f_m = f_{m-1}+f_{m-2}+\ldots+f_{m-k}\)
- 若m == k-1, \(f_m\) = 1
- 若m < k-1, \(f_m\) = 0
- 若k < 2 || m < 0, 不存在
题解
方法一：
就是按照递推式写就行了
方法二：
递归，边界条件为m\(\le\)k-1.
代码
直接把老师的代码复制过来了
1 2 3 4 5 6 7 8 9 10 11 12
| int Fib ( int m, int k) { if ( k < 2 || m< 0) return -1; if ( m < k-1) return 0; else if ( m == k-1 ) return 1; else { sum = 0; for( i = 1; i <= k; i++) sum += Fib( m - i, k); return sum; } }
|
优化
时间复杂度的优化：
当m\(\ge\)k-1时：
\(f_m = f_{m-1}+f_{m-2}+\ldots+f_{m-k}\),发现后面的k-1项是\(f_{m-1}\)的展开的前k-1项。于是从后面借一项\(f_{m-(k+1)}\).
可化简为：
\(f_m = 2*f_{m-1}-f_{m-(k+1)}\)
空间复杂度的优化：
由于递推式，第m项只和前k项有关，因此k项前面的可以覆盖。使用循环的数组来管理(模数)。
代码
递归版：
1 2 3 4 5 6 7 8
| int Fib ( int m, int k) { if ( k < 2 || m< 0) return -1; if ( m < k-1) return 0; else if( m == k-1 || m == k ) return 1; else return 2*Fib( m-1, k) – Fib( m-k-1, k); }
|
递推版：通项公式未化简，仅优化空间的：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| int Fib (int k, int m) { if (k<2 || m<0) return -1; if (m<k-1) return 0; else if (m == k-1) return 1; else{ int temp[k]; for(i=0; i<=k-2; i++) temp[i] = 0; temp[k-1] = 1; for(i=k; i<=m; i++){ sum = 0; for(j=0; j<k; j++) sum += temp[j]; temp[i%k] = sum; } r=temp[m%k]; return r; } }
|
优化了时间和空间的递推版：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| int Fib(int k, int m) { if (k<2 || m<0) return -1; if (m<k-1) return 0; else if ((m == k-1) || (m == k)) return 1; else { int temp[k]; for(i=1; i<=k-2; i++) temp[i] = 0; temp[0] = temp[k-1] = 1; s = 0; for(i=k+1; i<=m; i++){ sum = 2*temp[(i-1)%k]-s; s = temp[i%k]; temp[i%k] = sum; } r=temp[m%k]; return r; } }
|
题目
有n种物品，第i种物品有\(a_i\)个。不同的物品同类不可区分，不同类的可区分。若在这些物品中取m个。有多少种取法？答案模M
题意
例如：
n = m = 3
{1, 2, 3}
3 = 0+0+3 = 0+1+2 = 0+2+1 = 1+0+2 = 1+1+1 = 1+2+0
题解
- 设计状态：dp[i+1][j]:从前面i种物品中取j件的方案数
- 状态转移方程：dp[i+1][j] = \(\sum_{k=0}^{min(a[i], j)} dp[i][j-k]\).表示从i种物品中取出k件，其他的从前面的i-1种物品中选j-k件
- 边界： dp[i][0] = 1;
- 结果：dp[n][m], 下标从0开始
优化状态转移方程
若按照前面的方程进行转移，那么时间复杂度是O\((n*m^2)\).
在j-1\(\ge\)a[i]的条件下。
\(\sum_{k=0}^{min(a[i], j)} dp[i][j-k]\) = \(\sum_{k=0}^{min(j-1, a[i])} dp[i+1][j-1]+dp[i][j]-dp[i][j-1-a_i]\)
时间复杂度降为O(nm).
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
| #include <bits/stdc++.h> using namespace std; int n, m; int a[MAX_N]; int dp[MAX_N][MAX_M]; void solve(){ for(int i=0; i<=n; i++) dp[i][0] = 1; for(int i=0; i<n; i++){ for(int j=0; j<=m; j++){ if(j-1>=a[i]){ dp[i+1][j] = (dp[i+1][j-1]+dp[i][j]-dp[i][j-1-a[i]]+M)%M; } else { dp[i+1][j] = (dp[i+1][j-1]+dp[i][j])%M; } } } printf("%d\n", dp[n][m]); } int main() { cout << "Hello world!" << endl; return 0; }
|
题目
划分数，计数dp的入门题，无优化
题意
- 给定一个数n, 将其划分成m个非负整数，求方案数,最后模M
- 例如：n = 4, m=3:4 = 1+1+2 = 1+3 = 2+2
题解
- 状态设计：dp[i][j]：j划分成i的方案数
- 状态转移： dp[i][j] = dp[i][j-i]+dp[i-1][j].实际的意义：若将n划分成m， 如果对于每个\(a_i\)>0,那么{\(a_i-1\)}就对应n-m的m划分。
若存在\(a_i == 0\)，那么就对应了n-1的m划分
- 边界：dp[0][0] = 1;
- 结果：dp[m][n]
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| int n, m; int dp[MAX_M][MAX_N]; void solve(){ dp[0][0] = 1; for(int i=1; i<=m; i++){ for(int j=0; j<=n; j++){ if(j-i>=0){ dp[i][j] = (dp[i-1][j]+dp[i][j-i])%M; } else{ dp[i][j] = dp[i-1][j]; } } } }
|
未解决的问题
困成傻逼，明天再校验吧emmmmm
2017年11月6日01:13:07
果然是有错误的，
另外突然还想到了大霸计算超几何分布其实也是一种计算的优化。
还有树状数组可以优化的例子。
待更新吧。。。。。。
