小鸡玩算法-力扣HOT100-动态规划(上)
一.爬楼梯
问题概述：
思路：
1级台阶1种情况，2级台阶2情况，3级台阶要么是2级台阶再爬1格，要么是1级台阶爬2格，所以是1级和2级情况和，同理4级台阶是3级和2级情况合。
代码：
class Solution { public int climbStairs(int n) { if(n==1){ return 1; } if(n==2){ return 2; } int[] a=new int[n]; a[0]=1; a[1]=2; for(int i=2;i<n;i++){ a[i]=a[i-1]+a[i-2]; } return a[n-1]; } }二.杨辉三角
问题概述：
思路：
每一行起始位置和对角线都为1。剩余的都是其上＋上左.
代码：
class Solution { public List<List<Integer>> generate(int numRows) { List<List<Integer>> a=new ArrayList<List<Integer>>(); for(int i=0;i<numRows;i++){ List<Integer> b=new ArrayList<Integer>(); for(int j=0;j<=i;j++){ if(j==0||i==j){ b.add(1); }else{ b.add(a.get(i-1).get(j)+a.get(i-1).get(j-1)); } } a.add(b); } return a; } }三.打家劫舍
问题概述：
不能连着俩个偷，要偷最多。
思路：
如果偷num[i]那么最大值就是num[i]+dp[i-2],如果不偷就是dp[i-1]
dp[n]代表偷到第n个位置的最大值
代码：
class Solution { public int rob(int[] nums) { int n=nums.length; if(n==1){ return nums[0]; } int[] dp=new int[n]; dp[0]=nums[0]; dp[1]=Math.max(nums[0],nums[1]); for(int i=2;i<n;i++){ dp[i]=Math.max(nums[i]+dp[i-2],dp[i-1]); } return dp[n-1]; } }四.完全平方数
问题概述：
给你一个整数n，返回和为n的完全平方数的最少数量。
思路：
最坏的情况是都由1组成。x为最小数量。
n=1,x=1 n=2,x=2 这是固定的,
当n=3时，1*1<3 2*2>4 所以dp[3]=dp[2]+1
当n=4时，1*1<4 2*2=4 所以dp[4]=dp[3]+1 or dp[0]+1
。。。
当n=13时，1*1<13 2*2=4<13 3*3<13 4*4>13 所以dp[13]=dp[12]+1 or dp[9]+1 or dp[4]+1
代码：
class Solution { public int numSquares(int n) { int[] dp=new int[n+1]; for(int i=1;i<=n;i++){ dp[i]=i; } for(int i=1;i<=n;i++){ for(int j=1;j*j<=i;j++){ dp[i]=Math.min(dp[i],dp[i-j*j]+1); } } return dp[n]; } }五.零钱兑换
问题概述：
思路：
类似爬楼梯的思路，amount为目标台阶，每一步只能走coins数组中的台阶数，dp[i]表示到达第i级台阶所需的最小步数，那么自然可以想到dp[i] = min( dp[ i-coins[j] ] )+1。
初值设为amount+1，便于判断最后结果能不能凑成，是否为-1。如果像前面完全平方数设为i,比如dp[5]=5,如果数组为[1,5]则更新为1,如果为[1]则还是5,但是如果是[3]，那初值还是5就没法判断结果是否为-1。
代码：
class Solution { public int coinChange(int[] coins, int amount) { int[] dp=new int[amount+1]; Arrays.fill(dp,amount+1); dp[0]=0; for(int i=1;i<=amount;i++){ for(int coin : coins){ if(i>=coin){ dp[i]=Math.min(dp[i],dp[i-coin]+1); } } } return dp[amount] > amount ? -1:dp[amount]; } }