算法辅助公式

最大公约数的求法

计算两个整数最大公约数 gcd(a,b) 的一种常见方法是欧几里得算法，即辗转相除法。其核心部分为：

gcd(a,b)=gcd(b,a mod b)

1
2
3

public static int gcd(int a, int b) {
  return b==0 ? a : gcd(b, a%b);
}

最小公倍数 a*b/gcd(a,b)

打家劫舍

用 \textit{dp}[i]dp[i] 表示前 ii 间房屋能偷窃到的最高总金额，那么就有如下的状态转移方程：

\textit{dp}[i] = \max(\textit{dp}[i-2]+\textit{nums}[i], \textit{dp}[i-1]) dp[i]=max(dp[i−2]+nums[i],dp[i−1])

边界条件为：

$$ \begin{cases} \textit{dp}[0] = \textit{nums}[0] & 只有一间房屋，则偷窃该房屋 \ \textit{dp}[1] = \max(\textit{nums}[0], \textit{nums}[1]) & 只有两间房屋，选择其中金额较高的房屋进行偷窃 \end{cases} { dp[0]=nums[0] dp[1]=max(nums[0],nums[1]) ​$$

只有一间房屋，则偷窃该房屋 只有两间房屋，选择其中金额较高的房屋进行偷窃 ​

最终的答案即为 $dp[n−1]$，其中 n 是数组的长度。