动态规划
mkfoyw opened this issue · 5 comments
mkfoyw commented
常用的一些动态规划的状态转移方式
mkfoyw commented
在一个全是由 0 或者 1 矩形中， 找出全为1所构成的最大正方形面积。
dp[i][j]: 表示以第 i 行 j 例为右下角所构成最大正方形的面积
dp[i][j]: = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
mkfoyw commented
数位dp
数位：把一个数字按照个、十、百、千等等一位一位地拆开，关注它每一位上的数字。如果拆的是十进制数，那么每一位数字都是 0~9，其他进制可类比十进制。
数位 DP：用来解决一类特定问题，这种问题比较好辨认，一般具有这几个特征：
- 要求统计满足一定条件的数的数量（即，最终目的为计数）；
- 这些条件经过转化后可以使用「数位」的**去理解和判断；
- 输入会提供一个数字区间（有时也只提供上界）来作为统计的限制；
- 上界很大（比如 ），暴力枚举验证会超时。
模版代码
int a[20]; //保存拆分的数位
ll dp[20][state]; //不同题目状态不同
ll dfs(int pos //枚举位置, /*state变量*/ ,bool lead/*前导零*/, bool limit /*数位上界变量*/) //不是每个题都要判断前导零
{
//递归边界，既然是按位枚举，最低位是0，那么pos==-1说明这个数我枚举完了
if(pos==-1) return 1;/*这里一般返回1，表示你枚举的这个数是合法的，那么这里就需要你在枚举时必须每一位都要满足题目条件，也就是说当前枚举到pos位，一定要保证前面已经枚举的数位是合法的。不过具体题目不同或者写法不同的话不一定要返回1 */
//第二个就是记忆化(在此前可能不同题目还能有一些剪枝)
if(!limit && !lead && dp[pos][state]!=-1) return dp[pos][state];
//判断是否存在枚举限制
int up=limit?a[pos]:9;
ll ans=0;
//开始计数
for(int i=0;i<=up;i++)
{if() ...
else if()...
ans+=dfs(pos-1,/*状态转移*/,lead && i==0,limit && i==a[pos]) //最后两个变量传参都是这样写的
}
//计算完，记录状态, 不要记录有限制的状态
if(!limit && !lead) dp[pos][state]=ans;
return ans;
}参考文章：
mkfoyw commented
K个逆序对数组
我们用 f(i,j) 表示数字1到i排列中恰好有 j 个逆序对。
在状态转移时， 我们考虑第i 个数字和逆序对个数的关系。
对于第 i 个数， 将其放置到 [1 .. i] 任意一个位置， i 种放置方法
- 将 i 放到第 i 个位置上， 不会增加 逆序数。
- 将 i 放到第 i-1 个位置上， 那么会增加1个逆序数
- 将 i 放到第 i-2 个位置上， 那么会增加2个逆序数
因此将数字 i 放到 [1...i] 的任意一个位置，那么其之后的数形成逆序对。
f(i,j) = f(i-1, j) + f(i-1, j-1) + f(i-1, j-2) + ...+ f(i-1, j-i+1)
此时时间复杂度为 (NNK) ， 那么有什么优化的方法吗？