贪心算法与动态规划
贪心算法与动态规划
动态规划的思想是根据前一阶段的结果，去动态地推倒下一个阶段的结果。一般都是用来求最优解，且存在重复子问题的情况。比如经典的青蛙跳台阶，每次可跳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];
}
}
动态规划难就难在找到站台转移方程，如果能写出来状态转移方程，问题就很简单了。
经典的动态规划问题还有矩阵的最小路径、最大子数组之和等等。
微信分享/微信扫码阅读
