分治和动态规划

分治和动态规划都是解决较大规模问题比较困难或者无法直接求解的场景下的策略，两者之间有相同点，也有不同点。

相同点：

(1) 原问题需要具有最优子结构性质；

(2) 解决思路都是将原问题分解成若干个规模较小的子问题。

不同点：

(1) 分治法要求子问题之间相互独立，子问题的分解中不能包含公共子问题；

(2) 动态规划是应对子问题之间有重复的解决方案；

(3) 分治法一般采用递归来求解；

(4) 动态规划一般采用迭代法通过自底而上求解，或者通过具有记忆功能的迭代自顶而下求解。

通过上述分析的相同点和不同点，我们能够在遇到问题的时候，选择合适的策略求解。

例题分析

分治法快速幂运算：

对于给定的底数和指数幂，直接暴力计算的话，时间复杂度为O(n)。

根据数学知识，可知：

a^(n + n) = a ^n * a^n

通过上述性质，可以使用分治法对暴力幂运算进行优化，优化之后的时间复杂度为O(log n)。代码如下：

def FastPow(a, b):
    ans = 1
    base = b
    while b:
        if b & 1:
        r *= base
        base *=base
        b >> 1
    return ans            

动态规划算法的LeetCode 例题：

一个机器人位于一个 m * n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

 

在这道题中，我们首先设定dp[i][j] 为start 到点(i, j) 的最优策略（也就是题目中要求解的不同路径数），首先dp[0][0] = 1。

由给定性质，只能向下或者向右可以得出，dp[0][j] 和dp[i][0] 均为1。

对于其他位置的点(i, j)：

因为只能向下走，所以唯一确定dp[i - 1][j] 对dp[i][j] 有贡献；

因为只能向右走，所以唯一确定dp[i][j - 1] 对dp[i][j] 有贡献。

由上述性质可得出递推公式：

dp[i][j] = dp[i][j - 1] + dp[i - 1][j]

在本题中，需要求解的只是给定问题的最优解，不是内部其他子问题的最优解，所以二维数组可以优化。

仔细观察递推公式可以发现，当前点(i, j) 只与本行当前位置之前的数据和上一行当前位置的数据有关。

即，上述存储解的空间可优化为一个一维的数组：

dp[n] = dp[n] + dp[n - 1]

算法的时间复杂度为O(m*n)，空间复杂度为O(n)。下面是代码：

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        cur = [1] * n
        for i in range(1, m):
            for j in range(1, n):
                cur[j] += cur[j - 1]
        return cur[-1]