贪心算法与动态规划

贪心算法与动态规划

动态规划的思想是根据前一阶段的结果,去动态地推倒下一个阶段的结果。一般都是用来求最优解,且存在重复子问题的情况。比如经典的青蛙跳台阶,每次可跳1阶或者2阶,跳上10级台阶有多少跳法。

这个题要求台阶跳法,第10台阶依赖于第8台阶和第9台阶(因为有1阶和2阶两种跳法),也就是说第10阶的跳法f(10)等于第9阶的跳法f(9)加上第8阶的跳法f(8),即f(10=f(9)+f(8)。通过这个公,我们就可以轻松算出来。

简单的算法则是递归调用和,但会涉及到重复计算,因此我们可以把计算过的放到hash表中存储起来。但效率最高的算法就是动态规划。下面是代码:

class Solution {
    public int numWays(int n) {
        if(n<=1) return 1;
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i=2;i<n+1;i++){
            dp[i] = (dp[i-1]+dp[i-2]) % 1000000007;
        }
        return dp[n];
    }

对于,动态规划,重要的是写出状态转移方程,即将当前状态转移到之前的状态上,上面的f(n)=f(n-1)+f(n-2)即是状态转移方程。

其次是要确定边界,上面的就是台阶1和台阶2.

动态规划虽然效率高,但是其基本思想是空间换时间。他需要额外的数组去保持当前状态值。上面用的是一维数组,下面就是用的二维数组。

再说一个例子,就是求两个字符串的最长公共子序列。也是一样。

字符串text1,字符串text2,  我们定义一个二维数组是dp[m][n]。对于某个位置dp[i][j]

当text1[i-1] = text2[j-1]时,dp[i][j] = dp[i-1][j-1] + 1;

当text2[i-1] 1= text2[j-1]时,dp[i][j] = max(dp[i-1][j],dp[j-1][i]);

这就是其状态转移方程。现在写下其代码:

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        int[][] dp = new int[m+1][n+1];
        for(int i=1;i<=m;i++){
            char a = text1.charAt(i-1);
            for(int j=1;j<=n;j++){
                char b = text2.charAt(j-1);
                if(a == b){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[m][n];
    }
}

动态规划难就难在找到站台转移方程,如果能写出来状态转移方程,问题就很简单了。

经典的动态规划问题还有矩阵的最小路径、最大子数组之和等等。

--------EOF---------
本文微信分享/扫码阅读