成都app制作开发,seo网站描述,免费网站推广软件下载,建站之星和凡科1 打家劫舍
你是一个专业的小偷#xff0c;计划偷窃沿街的房屋。每间房内都藏有一定的现金#xff0c;影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统#xff0c;如果两间相邻的房屋在同一晚上被小偷闯入#xff0c;系统会自动报警。
给定一个代表每个房…1 打家劫舍
你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组计算你 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。 示例 1
输入[1,2,3,1]
输出4
解释偷窃 1 号房屋 (金额 1) 然后偷窃 3 号房屋 (金额 3)。偷窃到的最高金额 1 3 4 。
示例 2
输入[2,7,9,3,1]
输出12
解释偷窃 1 号房屋 (金额 2), 偷窃 3 号房屋 (金额 9)接着偷窃 5 号房屋 (金额 1)。偷窃到的最高金额 2 9 1 12 。
思路动态规划
1、边界条件
当只有一间房时则只能偷窃该房
当只有两件房时则选择偷窃金额大的房间 2、动态规划方程
当偷窃第K间房时不能偷窃第k-1间房总金额为前k-2间房的最高金额加上第K间房的金额之和
当偷窃第K-1间房时偷窃总金额为前k-1间房的最大总金额
dp[i] max【dp(i-2) nums[i] dp(i-1)】
代码
class Solution {public int rob(int[] nums) {// 数组判空if(nums null || nums.length 0){return 0;}int length nums.length;if(length 1){return nums[0];}// 定义动态规划数组 并用于返回最终结果int[] dp new int[length];// 定义边界条件dp[0] nums[0];dp[1] Math.max(nums[0], nums[1]);// 循环数组 从第三间房开始循环for(int i 2; i length; i){dp[i] Math.max(dp[i-2] nums[i], dp[i-1]);}return dp[length-1];}
} 2 完全平方数
给你一个整数 n 返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数其值等于另一个整数的平方换句话说其值等于一个整数自乘的积。例如1、4、9 和 16 都是完全平方数而 3 和 11 不是。 示例 1
输入n 12输出3
解释12 4 4 4
示例 2
输入n 13输出2
解释13 4 9
方法一动态规划
规划方程 这里不理解的点为什么在后面f[i] minn 1?fangfa
class Solution {public int numSquares(int n) {// 初始化数组 用于存储动态规划过程中的结果int[] f new int[n 1];f[0] 0; // 0*0 0for(int i 1; i n; i){// 初始化一个变量用于存储最小平方和int minn Integer.MAX_VALUE;// 从1 开始遍历 求平方和for(int j 1; j * j i; j){minn Math.min(minn, f[i - j * j]);}f[i] minn 1;}return f[n];}
} 方法二数学【四平方和定理】
