c 和 cpp 版整理动态规划笔记 _动态规划算法

爬楼梯一：动态规划
优化之后的程序
int climbStairs(int n) {int p = 0, q = 0, r = 1;for (int i = 1; i <= n; ++i) {p = q;q = r;r = p + q;}return r;}
二：矩阵快速幂（参考力扣）
以上的方法适用于 n 比较小的情况，在 n 变大之后，O(n) 的时间复杂度会让这个算法看起来有些捉襟见肘。我们可以用「矩阵快速幂」的方法来优化这个过程

得

令

因此我们只要能快速计算矩阵 M的 n 次幂，就可以得到 f(n) 的值。如果直接求取，时间复杂度是 O(n) 的，我们可以定义矩阵乘法，然后用快速幂算法来加速这里
如何想到使用矩阵快速幂？

我们可以做这样的变换：

令x
，那么我们又得到了齐次线性递推：

于是就可以使用矩阵快速幂求解了。当然并不是所有非齐次线性都可以化成齐次线性，我们还是要具体问题具体分析。
以下是矩阵快速幂的代码实现
struct Matrix {long long mat[2][2];};struct Matrix multiply(struct Matrix a, struct Matrix b) {// 矩阵 a*bstruct Matrix c;for (int i = 0; i < 2; i++) {for (int j = 0; j < 2; j++) {c.mat[i][j] = a.mat[i][0] * b.mat[0][j] + a.mat[i][1] * b.mat[1][j];}}return c;}struct Matrix matrixPow(struct Matrix a, int n) {// a 是 f(1) f(2)struct Matrix ret;// Mret.mat[0][0] = ret.mat[1][1] = 1;ret.mat[0][1] = ret.mat[1][0] = 0;while (n > 0) {if ((n & 1) == 1) {ret = multiply(ret, a);// ret = ret*a}n >>= 1;// -->n/2a = multiply(a, a);}return ret;}int climbStairs(int n) {struct Matrix ret;ret.mat[1][1] = 0;ret.mat[0][0] = ret.mat[0][1] = ret.mat[1][0] = 1;struct Matrix res = matrixPow(ret, n);// ret 的 n 次方return res.mat[0][0];}
三：通项公式
之前的方法我们已经讨论了f(n)是齐次线性递推，根据递推方程
，我们可以写出这样的特征方程：

求得
，
设通解为
，代入初始条件
，
，得
，
，我们得到了这个递推数列的通项公式：

【c 和 cpp 版整理动态规划笔记】接着我们就可以通过这个公式直接求第 n 项了
int climbStairs(int n) {double sqrt5 = sqrt(5);double fibn = pow((1 + sqrt5) / 2, n + 1) - pow((1 - sqrt5) / 2, n + 1);return (int) round(fibn / sqrt5);}
总结：矩形盖
仔细观察是斐波拉契问题
某一次的结果可以是由一块叠来的，也可以是由两块小的叠来的
字符串问题
给定一个由0-9组成的字符串，1可以转化成A，2可以转化成B 。依此类推。。25可以转化成Y，26可以转化成z，给一个字符串，返回能转化的字母串的有几种？
两种转化方法
矩阵问题：
给一个由数字组成的矩阵，初始在左上角，要求每次只能向下或向右移动，路径和就是经过的数字全部加起来，求可能的最小路径和

分析：我们可以像之前一样，暴力的把每一种情况都试一次，但是依旧会造成过多的重复计算，以本题为例子最后解释一下暴力慢在哪里，以后不再叙述了
从1到6有很多路可走
将A到某个点的最小距离之和填入以下表格
优化空间复杂度（重新开辟一行空间，用来存储步数）
B：9 是 A 的（从左面走过来），4 是上面的（从上面走下来的），1 是这个格子本来的
// 遍历原矩阵// 初始化// #define MAX_SIZE 100int min(int a, int b) {return a>b?b:a;}int minPath(int nums[][4], int numsLine, int numsCol) {// 按道理要分情况int a[MAX_SIZE];int flag = 0;for(int i = 0; i < numsCol; ++i) {a[i] = nums[0][i]+flag;flag = a[i];}for(int i = 1; i < numsLine; ++i) {for(int j = 0; j < numsCol; ++j){if(j)a[j] = min(a[j-1], a[j]);a[j] += nums[i][j];}}return a[numsCol-1];}
给一个由数字组成的矩阵，初始在左上角，要求每次只能向下或向右移动，路径和就是经过的数字全部加起来，求可能的最大路径和
一个矩阵，初始在左上角，要求每次只能向下或向右移动，求到终点的方法数（将最大最小路径简化了，第一行第一列是1，之后用min计算即可）
代码实现如下
#define MAX_SIZE 100int max(int a, int b) {return a>b?a:b;}int minWay(int numsLine, int numsCol) {// 按道理要分情况int a[MAX_SIZE];// 计算小的情况就可以了int mAx = max(numsLine, numsCol);int min = numsLine + numsCol - mAx;for(int i = 0; i < min; ++i)a[i] = 1;for(int i = 1; i < mAx; ++i) {for(int j = 1; j < min; ++j){a[j] = a[j-1]+a[j];}}return a[min-1];}
暗黑字符串：判断字符串纯净还是暗黑（网易17校招）
参考牛客网
刷格子（蓝桥杯）
问题描述古国的一段古城墙的顶端可以看成 2×N个格子组成的矩形（如下图所示），现需要把这些格子刷上保护漆。例如下图是一个长度为3，高为2的城墙
你可以从任意一个格子刷起，刷完一格，可以移动到和它相邻的格子（对角相邻也算数），但不能移动到较远的格子（因为油漆未干不能踩！）比如： a d b c e f 就是合格的刷漆顺序。c e f d a b 是另一种合适的方案。当已知 N 时，求总的方案数。当n较大时，结果会迅速增大，请把结果对(十亿零七) 取模。
输入格式：输入数据为一个正整数（不大于1000）输出格式：输出数据为一个正整数。
样例输入：2 样例输出：24 样例输入：3 样例输出：96 样例输入：22 样例输出：
题解：
从四个顶点出发时
第一步走同一列的另一个格子，然后再向走下一列，并不断重复这个过程。
走完一个直接去下一列，走到最后一列直接返回（有back）
两列两列走，走完一个去下一列，回到上一列，再去下一列
总结：
a[i] = 2*a[i-1]+b[i]+2 *2 *a[i-2];

c 和 cpp 版 整理动态规划笔记

c 和 cpp 版整理动态规划笔记