写一个动态规划的算法

写一个动态规划的算法

递归是从上往下的计算，递归中有大量的重复计算，以斐波那契为例

动态规划是子上往下的解决问题，先解决小数据量下的结果层层类推，解决大数据规模下的问题

动态规划的思路：将原问题拆解成若干的子问题，同时保存子问题的答案，使得每个子问题只求解一次，最终获得原问题的答案。

有时候自顶向下的思考问题很容易，动态规划首先自顶向下的思考问题，然后用子底向上的实现。

    public int fib(int n){

        int[] memo = new int[n + 1];
        Arrays.fill(memo, -1);

        memo[0] = 0;
        memo[1] = 1;
        for(int i = 2 ; i = 0)
            if(s1.charAt(m) == s2.charAt(n)){
                res.insert(0, s1.charAt(m));
                m --;
                n --;
            }
            else if(m == 0)
                n --;
            else if(n == 0)
                m --;
            else{
                if(memo[m-1][n] > memo[m][n-1])
                    m --;
                else
                    n --;
            }

        return res.toString();
    }

动态规划与贪心算法的关系

通常贪心算法代码会非常的段而且思路很清晰，但是贪心算法难点在于确定可以使用贪心算法能解决。

给小朋友送饼干，每个小朋友能得到一块饼干，每个饼干有一个大小值s(i)，每个学生有一个贪心指数g(i)，必须s(i)要大于g(i)

如果当前最大的饼干都无法满足最贪心的小朋友说明所有的都无法满足，每次尝试使用剩下最大的饼干，最大程度保证所有小朋友都开心

    public int findContentChildren(int[] g, int[] s) {

        Arrays.sort(g);
        Arrays.sort(s);

        int gi = g.length - 1, si = s.length - 1;
        int res = 0;
        while(gi >= 0 && si >= 0){
            if(s[si] >= g[gi]){
                res ++;
                si --;
            }
            gi --;
        }

        return res;
    }

    public int findContentChildren(int[] g, int[] s) {

        Arrays.sort(g);
        Arrays.sort(s);

        int gi = 0, si = 0;
        int res = 0;
        while(gi < g.length && si < s.length){
            if(s[si] >= g[gi]){
                res ++;
                gi ++;
            }
            si ++;
        }

        return res;
    }

贪心算法与动态规划

给定一组区间，问最少删除多少个区间，让这些区间之间互相不重叠

与最长上升子区间的比较，每一次根前面区间的后面比较，然后+1

先排序才能判断不重叠

    // Definition for an interval.
    public static class Interval {
        int start;
        int end;
        Interval() { start = 0; end = 0; }
        Interval(int s, int e) { start = s; end = e; }
    }

    public int eraseOverlapIntervals(Interval[] intervals) {

        if(intervals.length == 0)
            return 0;

        Arrays.sort(intervals, new Comparator() {
            @Override
            public int compare(Interval o1, Interval o2) {
                if(o1.start != o2.start)
                    return o1.start - o2.start;
                return o1.end - o2.end;
            }
        });

        // memo[i]表示以intervals[i]为结尾的区间能构成的最长不重叠区间序列
        int[] memo = new int[intervals.length];
        Arrays.fill(memo, 1);
        for(int i = 1 ; i < intervals.length ; i ++)
            // memo[i]
            for(int j = 0 ; j < i ; j ++)
                if(intervals[i].start >= intervals[j].end)
                    memo[i] = Math.max(memo[i], 1 + memo[j]);

        int res = 0;
        for(int i = 0; i < memo.length ; i ++)
            res = Math.max(res, memo[i]);

        return intervals.length - res;
    }