在介绍动态规划的核心思想前，先看一道题。
题目分析：
令dp[i]代表有多少种方法可到达第i层，
由于第i层只能由i-1走一层或者i-2走两层达到，
故可得dp[i] = dp[i-2] + dp[i-1]，
很明显根据题意dp[1] = 1,dp[2] = 2。
dp[0]哪去了？为了我们写起来好看，浪费掉了。
如果喜欢你也可以用dp[0] = 1, dp[1] = 2,只是最后结果是dp[i-1]而不是dp[i]就是了。
解法一：递归
public static int climbStairs_recursion(int n){
if(1 == n)
return 1;
else if(2 == n)
return 2;
return climbStairs_recursion(n-2) + climbStairs_recursion(n-1);
}
解法一分析
解法一存在一个问题，
因为dp[i] = dp[i-2] + dp[i-1]，则dp[i-1] = dp[i-3] + dp[i-2]，
此刻dp[i-2]重复出现了两次。
关键就在这里，这个重复的dp[i-2]并非重复一次这么简单，
因为dp[i-2]又是由dp[i-4]+dp[i-3]得到，层层递归下去，将是2^(i-2)次函数调用，
举一个例子，当i=30时候，dp[i]将会调用函数1664079次！
解法二：递归-动态规划
public static int climbStairs_dp_recursion(int n, int[] dp){
if(1 == n)
return 1;
else if(2 == n)
return 2;
if(0 == dp[n])
dp[n] = climbStairs_dp_recursion(n-2, dp) + climbStairs_dp_recursion(n-1, dp);
return dp[n];
}
解法二分析
1.使用一个数组来缓存了中间结果，防止了“重叠子问题”的重复计算。
2.解法二依然存在一个问题，就是在于“递归”这种写法，递归产生的函数调用将消耗线程栈内存。
使用-Xss180k作为虚拟机启动参数将线程栈设置为180k（jvm允许的最小值），
并将问题规模n设置为3000，就会出现Stack Over flow。
解法三：循环-动态规划
public static int climbStairs_dp_loop(int n){
if(1 == n)
return 1;
else if(2 == n)
return 2;
int[] dp = new int[n+1];
int res = 0;
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i < n+1; i++) {
res = dp[i] = dp[i-2] + dp[i-1];
}
return res;
}
解法三分析
1.解决方法是改为循环，
因为递归和循环永远可以相互转换，请不要怀疑“永远”这个词的严谨性。
2.最后还有一个可优化的点，内存使用。
我们使用dp[i] = dp[i-2] + dp[i-1]这个式子，循环递推出结果，
dp[i]使我们想要的结果，而只需要dp[i-2]和dp[i-1]得到，
然而我们却保留了i个也就是所有递推过程的中间结果，显然这是一种浪费。
解法四：循环-动态规划-内存优化
public static int climbStairs_dp_loop_lessMemory(int n){
if(1 == n)
return 1;
else if(2 == n)
return 2;
int res = 0;
int temp1 = 1;
int temp2 = 2;
for (int i = 3; i < n+1; i++) {
res = temp1 + temp2;
temp1 = temp2;
temp2 = res;
}
return res;
}
解法四分析
通过两个变量的交替更新使用，达到了节约内存的目的，
这种不断更新两个变量的做法，就像将整个数组“滚动”起来了一样，在动态规划中称为“滚动数组”。
这里不用担心我们丢掉的结果，因为题目只求最后的值。
总结
1.将结果集合之间的关系描述为“动态转换方程”。
动态规划的所有核心都在这一步。
在做dp时，
不要关注数据和最终结果的关系。
关注结果集合之间的关系！
结果集合指什么，此题中所有dp[i]的值的集合就是结果集合。
我们找到的dp[i] = dp[i-2] + dp[i-1]，就是结果集合之间的关系。
这个关系就是"动态转换方程"。
2.构造递推初始项。
3.缓存推导过程中的“重叠子问题”，防止重复计算。
4."滚动使用变量或数组"是常见的dp内存优化方式。
相应例题的 Github
网友评论