动态规划

主要思想是将复杂问题(带有许多递归分析)分解为更小的子问题，然后保存到内存当中，这样就不需要在每次使用的时候重复进行计算

例如斐波那契数列的计算，计算F(5)的时候需要知道F(3)和F(4)，而计算F(4)需要知道F(3)和F(2),以此类推往下，就会有很多重复的计算，例如这里F(3)就会被计算了两遍，所以我们要想办法将F(3)存储起来，即在计算F(4)的时候获得的F(3)能够在计算F(5)时接着使用，就变成了常量相加，意味着序列中每个单独元素的计算都是O(1)

动态规划的三个步骤：

确定适用于所述问题的递归关系
初始化内存、数组、矩阵的初始值
确保当我们进行递归调用时可以访问到子问题的答案

这时看一个例子
Leecode 青蛙跳台阶问题

一只青蛙一次可以跳上一级台阶，也可以跳上2级台阶，求该青蛙跳上一个10级台阶总共有多少种跳法

思路就是，跳上第10阶有两种可能，即在第九级往上跳一次，或者在第八级往上跳两级，即F(10) = F(9) + F(8),同理可以往下推，其实就有点像斐波那契数列了

可以使用递归解法

java
class Solution {
    public int numWays(int n){
        if(n==1) return 1;
        if(n==2) return 2;
        return numWays(n-1)+numWays(n-2);
    }
}

去解题时发现，报错StackOverflow，该递归的时间复杂度较高

递归时间复杂度 = 解决一个子问题时间 * 子问题个数

一个子问题时间 = f(n-1) + f(n-2),即O(1)，但是问题个数=递归树节点的总数，递归树节点的总数为2^n-1

所以时间复杂度为O(2^n),即指数级别，如果n比较大的话，就很容易超时了

这时候就有另外一种解法，即备忘录解法,即对递归树进行剪枝，去掉一些重复计算的部分，思路就是F(10)=F(9)+F(8),那就将F(9)和F(8)存于备忘录，所以需要去计算F(9)和F(8)的值，所以到最后是先将F(9)计算出来，即计算了F(1)-F(9)的值，那其他计算就是直接从备忘录里中取值，速度就快了好多

java
class Solution {
    HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
    public int numWays(int n){
        // 递归解法--这里会超时或栈溢出，递归过多了
        // if(n==1) return 1;
        // if(n==2) return 2;
        // return numWays(n-1)+numWays(n-2);

        // 备忘录解法
        // HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        if(n==0) return 1;
        if(n<=2) return n;
        if(map.containsKey(n)) {
            return map.get(n);
        }else {
            // 备忘录不存在则计算并加入备忘录
            map.put(n,(numWays(n-1)+numWays(n-2))%1000000007);
            return map.get(n);
        }
    }
}

接下来就是讲一下关于动态规划的解法，与备忘录的思路类型，不过备忘录是自顶向下，而动态规划是自底向上的解法，从F(1)往F(10)方向求解

动态规划有几个典型特征

最优子结构

f(n-1)和f(n-2)称为最优子结构
状态转移方程

f(n)=f(n-1)+f(n-2)就是状态转移方程
边界

f(1) = 1,f(2) = 2就是边界
重叠子问题

f(10) = f(9) + f(8),f(9) = f(8) + f(7)，f(8)就是重叠子问题

动态规划有一个基本的框架

js
# 初始化 base case
dp[0][0][...] = base
for 状态1 in 状态1的所有取值:
    for 状态2 in 状态2的所有取值:
        for ...
            dp[状态1][状态2][...] = 求最值(选择1,选择2...)

在这道题就是

java
int[] dp = new int[n+1];
dp[1] = dp[2] = 1;
for (int i = 3;i<=n;i++){
    dp[i] = dp[i-1]+dp[i-2];
}
return dp[n];

接下来还可以进行状态压缩，即只需要用到dp表的某个固定长度的值，则可以减少空间的使用

java
int a = 1,b = 2;
for(int i = 3;i<=n;i++){
    int sum = a+b;
    a = b;
    b = sum;
}

接下来刷一道难一点的题目
[Leecode 72 编辑距离](uhttps://leetcode.cn/problems/edit-distance/

给你两个单词 word1 和 word2，请返回将 word1 转换成 word2 所使用的最少操作数。

你可以对一个单词进行如下三种操作：

插入一个字符

删除一个字符

替换一个字符

这道题呢我们已经知道是用动态规划了，那就想怎么进行，首先是dp如何定义，dp[i][j]自然是计算出来的最少操作次数，那i和j呢，在这里是对应word1和word2的第[i]个和第[j]个单词，这个没有什么诀窍，写久了自然能看出来

那状态转移方程怎么写

像dp表，我们从前往后遍历，所以新增的一定是在单词串的最后，即每次新增一个改怎么操作，其实无非就是增删改三种操作选一种

所以f[i][j] = Math.min(增加前的状态，删除前的状态，修改前的状态)+1

那增加前的状态是什么，我们知道，增加的话自然是增加一个最新的word2[j],即求word1[0...i]转为word2[0...j-1]的次数

而删除也类似，即word1删除了word1[i]，求word[0...i-1]转为word2[0...j]的次数

修改则是两个都去掉，改为求word[0...i-1]转为word2[0...j-1]的次数

当然还有一种情况，类似修改的，即新增的word1[i]==word2[j]，那就不需要进行额外的操作，直接dp[i][j]=dp[i-1][j-1]

java
class Solution {
    public int minDistance(String word1, String word2) {
        // 三种操作 插入，删除，替换
        // 先定义dp表的元素含义，值肯定是最少操作数，那i和j呢，应该可以代表word1和word2的长度

        int[][] dp = new int[word1.length()+1][word2.length()+1];
        // 首先(0,0) 为 0
        // 如果word1[i] 与word2[j] 相等，则无须进行操作，即dp[i][j] = dp[i-1][j-1]
        // 如果不等的话，则要进行调整，即三选一，word[i]改为word[j]，则dp[i][j] = dp[i-1][j-1]
        // 如果插入的话，则dp[i][j] = dp[i][j-1] + 1
        // 如果删除的话，则dp[i][j] = dp[i-1][j] + 1

        for(int i = 1;i<word1.length()+1;i++) {
            dp[i][0] = dp[i-1][0] + 1;
        }
        for(int j = 1;j<word2.length()+1;j++) {
            dp[0][j] = dp[0][j-1] + 1;
        }

        for(int i = 1;i<word1.length()+1;i++) {
            for(int j = 1;j<word2.length()+1;j++) {
                // 即在末尾加上了一个一样的，所以和去掉时所需要进行的操作没差别
                if(word1.charAt(i-1) == word2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1];
                    continue;
                }
                //如果是加上了不一样的，则类似于在上一个的情况进行增删改
                // 增加即在a的末尾加上当前b新加上的字符，即求a转为b去掉当前字符的次数再加1
                // 删除则是将a的末尾删掉后直接转为b再加1
                // 修改则是两个都去掉，即直接将word1[i]转为word2[j]，然后再加上去掉后的直接转换的次数
                dp[i][j] = Math.min(dp[i-1][j-1],dp[i-1][j]);
                dp[i][j] = Math.min(dp[i][j],dp[i][j-1]) + 1;
            }
        }
        return dp[word1.length()][word2.length()];
    }
}

目录

动态规划