Dynamic Programming (动态规划) 动态规划思想,是用已知的规律,从历史数据计算出未来的最优解,这种方法省去暴力算法中的不必要的样本空间,非常重要。 爬楼梯 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 示例 1: 输入:n = 2 输出:2 解释:有两种方法可以爬到楼顶。 1 阶 + 1 阶 2 阶 示例 2: 输入:n = 3 输出:3 解释:有三种方法可以爬到楼顶。 1 阶 + 1 阶 + 1 阶 1 阶 + 2 阶 2 阶 + 1 阶 提示: 1 <= n <= 45 解题思路 N级台阶的解来自之前N-1级台阶的各自解之和,可以尝试创建动态规划的转移方程。首先尝试罗列出部分基础数值: f(0)=1 //也可以不考虑0的情况,因为题目说了n>=1,这样的话,程序就应该从f[1]+f[2]开始 f(1)=1 f(2)=1+1=2 //全部一级级走(1)+ 只走2级(1) f(3)=1+1+1=3 //全部一级级走(1)+ 先2次一级再2级1次(1)+ 先2级1次再1级1次(1) f(4)=1+1+1+1+1=5 //全部一级级走(1)+ 先2次一级再2级2次(1)+ 先3次一级再2级1次(1) + 先2级1次再1级2次(1)+ 先2级1次再2级1次(1) .

Continue reading

矩阵基础回顾

加法: 矩阵的加法中,双方必须是同型矩阵(A行列与B行列全部相等)才可进行运算。 矩阵加法只要对应位直接相加即可,Aij + Bij = Cij 乘法: 若A是M x S (M行S列)矩阵,乘以B(S x N)矩阵,则会得到C(M x N)矩阵。 乘法中,不要求两个矩阵同型。但第一个矩阵的S列数一定要等于第二个矩阵的S行数。 乘法是用A的行1中A11 A12 A13…Ams 乘以B矩阵的列1中B11 B21 B31…Bsn 作为C的C11,然后用A11 A12 A13乘以B的第二列B12 B22 B32作为C的C12。即A的i行乘以B的j列得出C中对应的Cij (ij<=mn)

Continue reading

Author's picture

Charles

Love coding and new technologies

Cloud Solution Consultant

Canada