小鸡玩算法-力扣HOT100-动态规划(上)

一.爬楼梯问题概述思路1级台阶1种情况2级台阶2情况3级台阶要么是2级台阶再爬1格要么是1级台阶爬2格所以是1级和2级情况和同理4级台阶是3级和2级情况合。代码class Solution { public int climbStairs(int n) { if(n1){ return 1; } if(n2){ return 2; } int[] anew int[n]; a[0]1; a[1]2; for(int i2;in;i){ a[i]a[i-1]a[i-2]; } return a[n-1]; } }二.杨辉三角问题概述思路每一行起始位置和对角线都为1。剩余的都是其上上左.代码class Solution { public ListListInteger generate(int numRows) { ListListInteger anew ArrayListListInteger(); for(int i0;inumRows;i){ ListInteger bnew ArrayListInteger(); for(int j0;ji;j){ if(j0||ij){ 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 nnums.length; if(n1){ return nums[0]; } int[] dpnew int[n]; dp[0]nums[0]; dp[1]Math.max(nums[0],nums[1]); for(int i2;in;i){ dp[i]Math.max(nums[i]dp[i-2],dp[i-1]); } return dp[n-1]; } }四.完全平方数问题概述给你一个整数n返回和为n的完全平方数的最少数量。思路最坏的情况是都由1组成。x为最小数量。n1,x1 n2,x2 这是固定的,当n3时1*13 2*24 所以dp[3]dp[2]1当n4时1*14 2*24 所以dp[4]dp[3]1 or dp[0]1。。。当n13时1*113 2*2413 3*313 4*413 所以dp[13]dp[12]1 or dp[9]1 or dp[4]1代码class Solution { public int numSquares(int n) { int[] dpnew int[n1]; for(int i1;in;i){ dp[i]i; } for(int i1;in;i){ for(int j1;j*ji;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。初值设为amount1便于判断最后结果能不能凑成是否为-1。如果像前面完全平方数设为i,比如dp[5]5,如果数组为[1,5]则更新为1,如果为[1]则还是5,但是如果是[3]那初值还是5就没法判断结果是否为-1。代码class Solution { public int coinChange(int[] coins, int amount) { int[] dpnew int[amount1]; Arrays.fill(dp,amount1); dp[0]0; for(int i1;iamount;i){ for(int coin : coins){ if(icoin){ dp[i]Math.min(dp[i],dp[i-coin]1); } } } return dp[amount] amount ? -1:dp[amount]; } }