算法基础复习-动态规划

1. 动态规划（Dynamic Programming，DP）

动态规划通常用来求解复杂问题的某个最优解，与分治法相似，区别在于

• 分治法应用于子问题互不相交的情况，即递归的每一步都生成全新的子问题
• 动态规划应用于重叠子问题的情况，即递归反复求解相同的子问题

使用条件

1. 最优子结构：问题的最优解由子问题的最优解组合而成，子问题可以独立求解
2. 重叠子问题：不同的子问题可能有公共的子子问题，导致反复求解相同的问题

实现方法

• 带备忘的自顶向下法（top-down with memoization）
  用数组或哈希表保存每个子问题的解，求解子问题时先看是否已经保存过
• 自底向上法（bottom-up）
  对于任何子问题，其子问题均已求解完成，才会求解它

两种方法核心都在于保持递归的流程同时，维护了一个表记录子问题的解

设计步骤

1. 考察问题是否具有最优子结构，刻画最优解的结构
2. 递归的定义，最优解的值
3. 计算最优解的值
4. 通常使用 bottom-up 法

1.1 最长公共子序列（Longest Common Subsequence，LCS）

LeetCode 1143题：
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        
        int m = text1.length();
        int n = text2.length();

        int[][] c = new int[m+1][n+1]; //构建dp表c，表示LCS长度，数组下标来表示序列中字符个数

        int i,j; // 用i表示A序列中的第i个字符，j表示B序列中的第j个字符

        for (i = 0; i <= m; i++) //当一个字符串长度为0时，LCS长度为0
            c[i][0] = 0;
        for (j = 0; j <= n; j++)
            c[0][j] = 0;

        for (i = 1; i <= m; i++) { //自底向上
            for (j = 1; j <= n; j++) {
                if (text1.charAt(i-1) == text2.charAt(j-1)) {
                    c[i][j] = c[i-1][j-1] + 1;
                } else {
                    c[i][j] = Math.max(c[i-1][j], c[i][j-1]);
                }
            }
        }

        return c[m][n];
    }
}

几乎所有的动态规划解决方案，首先会创建一个一维或多维数组 DP来保存中间子解的值，以及通常数组最后一个值代表最终解

• 当存在一个字符串为空串时，LCS不存在，长度等于0
• 用索引0表示了空串，因此DP表初始化为 dp[str1.length()+1][str2.length()+1]

• 状态转移方程

2. 贪心算法

在当前步做出看起来最佳的选择，不依赖于子问题的解，最终可能获得全局最优解
动态规划每步都要进行一次选择，通常依赖于当前步子问题的解

使用条件

1. 贪心选择性质：不需要考虑子问题的解，就可做出当前问题看起来最优的选择
2. 最优子结构

设计步骤

1. 做出一次选择后，只剩下一个子问题需要求解
2. 贪心选择后，原问题总是存在最优解
3. 剩余子问题最优解与贪心选择组合即可获得原问题的最优解
4. 通常使用 top-down 法

2.1 最小生成树

图的生成树：一个无向图的极小连通子图，它有n个顶点，n-1条边
最小生成树：以最小代价构成的极小连通子图

2.1.1 Kruskal 算法

每次都选择权重最小的边（贪心选择），排除掉会构成环的边，最终构成最小生成树

代码核心

• 并查集：Find 查询两个元素是否在同一个集合中，Union 把两个不相交的集合合并为一个集合
• 权重排序（Java使用Collections工具类，对ArrayList<Edge>中的edge按权重排序）

LeetCode 1584题：

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

/**
 * @author CodfishXY
 * @program: Kruskal
 * @description: 最小连接代价
 * @date 2020-10-25 18:00
 */
public class MinCostConnectPoints {

    int[] parent; //声明并查集数组，即父节点数组

    //定义并查集中用来查找根节点的方法，这样就能判断一条边的顶点是否来自同一个根节点
    public int findRoot(int x){
        return parent[x] == x ? x : findRoot(parent[x]); //递归查找x的根节点，因为根节点没有父节点，所以当查到的父节点为其自身时，这个结点就是根节点
    }

    public int mccp(int[][] points) {

        int v = points.length; //顶点个数，即坐标个数
        int w = 0; //计算出的权值，即曼哈顿距离
        int result = 0; //最终结果

        parent = new int[v]; //初始化父节点数组，用来存储每个顶点的父节点
        for (int k = 0; k < v; k++) { //先把每个顶点的父节点初始化为其自身
            parent[k] = k;
        }

        //定义存放边的数组
        ArrayList<Edge> edges = new ArrayList();
        for (int i = 1; i < v; i++) {
            for (int j = 0; j < i; j++) {
                w = Math.abs(points[i][0] - points[j][0]) +
                        Math.abs(points[i][1] - points[j][1]);
                edges.add(new Edge(i, j, w));
            }
        }

        //按权重排序边
        //List排序知识：Collections是一个工具类，sort是其中的静态方法，专门用来对List类型进行排序
        Collections.sort(edges, new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.compareTo(o2);
            }
        });

        //比较边的两个顶点是拥有同一个根节点
        for (int m = 0; m < edges.size(); m++) {
            if (findRoot(edges.get(m).begin) != findRoot(edges.get(m).end)) {
                result += edges.get(m).weight;  //添加成功，计算当前权值
                parent[findRoot(edges.get(m).begin)] = findRoot(edges.get(m).end); //合并，即让一个根结点指向另一个根结点
            }
        }

        return result;

    }
}

class Edge implements Comparable<Edge> {

    int begin;
    int end;
    int weight;

    public int getBegin() {
        return begin;
    }

    public void setBegin(int begin) {
        this.begin = begin;
    }

    public int getEnd() {
        return end;
    }

    public void setEnd(int end) {
        this.end = end;
    }

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }

    public Edge(int begin, int end, int weight) {
        this.begin = begin;
        this.end = end;
        this.weight = weight;
    }

    public Edge() {
    }

    @Override
    public int compareTo(Edge o) {
        return Integer.compare(this.weight, o.weight);
    }

    @Override
    public String toString() {
        return "Edge{" +
                "begin=" + begin +
                ", end=" + end +
                ", weight=" + weight +
                '}';
    }
}