万物的开始,首先介绍一下动态规划(dynamic programming,DP)的基本服务器托管网概念:动态规划适用于有重叠子问题和最优子结构性质的问题,并且记录所有子问题的结果,因此动态规划方法耗费时间远远少于朴素解法。
动态规划总共可以分为4个步骤:1、定义子问题 2、写出子问题的递推关系 3、确定DP数组的计算顺序。4、空间优化。
步骤1:子问题与原问题相似,但是规模很小。子问题是参数化的,假设定义的子问题中参数为k。假设有n个房子,总共有n个子问题。动态规划实际上就是通过求解一堆子问题的解,来找出原问题的解。一个子问题的解是可以通过其他子问题的解求出。例如这道小偷问题中,f(k) 可以由 f(k – 1)和f(k – 2)求出。
步骤2:写出子问题的递推关系。设置有k间房子,那么偷k个房子,则有2种偷法,要不第k间房子被偷,要不第k-1间房子被偷。注意在写,递推关系的时候,写上边界情况,比如k = 0,k = 1的值。
步骤3:确定DP数组的计算顺序。此外,动态规划有自底向上和自顶向下两种解决问题的方法,自顶向下是记忆化(备忘录)递归,自底向上是递推、使用DP数组的循环方法。DP 数组也可以叫”子问题数组”,那么,只要搞清楚了子问题的计算顺序,就可以确定 DP 数组的计算顺序。对于小偷问题,我们分析子问题的依赖关系,发现每个f(k) 依赖 f(k -1) 和 f(k – 2)。也就是说, dp[k] 依赖 dp[k-1] 和 dp[k-2]。
步骤4:空间优化的基本原理是,很多时候并不需要始终持有全部的 DP数组。对于小偷问题,我们发现,最后一步计算 f(n)的时候实际上只用到了 f(n-1)和 f(n- 2)的结果,n- 3之前的子问题,实际上早就已经用不到了。那么,可以只用两个变量保存两个子问题的结果,就可以依次计算出所有的子问题。
class Solution { public int rob(int[] nums) { // 长度为空 if(nums.length == 0) return 0; int N = nums.length; int[] dp = new int[N+1]; dp[0] = 0; 服务器托管网 dp[1] = nums[0]; for(int k = 2;k
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.fwqtg.net
相关推荐: leetcode 283 移动零 move-zeroes【ct】
=== 思路: 首先保存len变量表示当前数组长度,遍历len,如果值为0,就去掉它,并推入到数组底部,注意需要len–和i– 服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net 机房租用,北京机房租用,IDC机房托管,…