浙江省建设网站,外贸订单从哪里接,网站开发参数,知名网站开发【爬楼梯】
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢#xff1f;
思路#xff1a; 【状态】 dp[i];//爬i级台阶有几种方法 【初始】 dp[0] 1;//爬0级1种#xff08;不爬#xff09;dp[1] 1;/…【爬楼梯】
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
思路 【状态】 dp[i];//爬i级台阶有几种方法 【初始】 dp[0] 1;//爬0级1种不爬dp[1] 1;//爬1级1种 【递推】 dp[i] dp[i-2] dp[i-1];//爬i级先爬i-1级再爬1级先爬i-2级再爬2级没有其他可能了 【结论】 dp[n];//爬n级方法数
class Solution {
public:int climbStairs(int n) {vectorint dp(n 1);dp[0] 1;dp[1] 1;for (int i 2; i n; i) {dp[i] dp[i - 1] dp[i - 2];}return dp[n];}
};
【杨辉三角】
给定一个非负整数 numRows生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中每个数是它左上方和右上方的数的和。
思路
观察示例可以发现
每一行的行号也是该行元素的最大下标
每行的首尾元素是1
其余元素是它左上和右上元素的和
把以上规则翻译成代码语言即可。
class Solution {
public:vectorvectorint generate(int numRows) {vectorvectorint ans;vectorint lastRow(1,1);ans.push_back(lastRow);if (numRows 1)return ans;for (int i 1; i numRows; i) {vectorint curRow;//当前行最大下标就是icurRow.push_back(1);for (int j 1; j i; j) {curRow.push_back(lastRow[j - 1] lastRow[j]);}curRow.push_back(1);ans.push_back(curRow);lastRow.resize(i1);lastRow curRow;}return ans;}
};
【打家劫舍】
你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组计算你 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。
思路
建立dp数组dp[i]代表到房子i为止最高可以偷到的金额。
对当前房子我们分别计算偷它和不偷它可以获得的最大金额并记录两者中较大的那个
偷它那么i-1号房子不可以偷总金额是偷i-2及以前的房子偷i
不偷它那么i-1房子可以偷总金额就是偷i-1及以前的房子
class Solution {
public:int rob(vectorint nums) {int n nums.size();if (n 1)return nums[0];vectorint dp(n, 0);dp[0] nums[0];dp[1] max(nums[0], nums[1]);for (int i 2; i n; i) {dp[i] max(nums[i] dp[i - 2], dp[i - 1]);}return dp[n - 1];}
};
【完全平方数】
给你一个整数 n 返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数其值等于另一个整数的平方换句话说其值等于一个整数自乘的积。例如1、4、9 和 16 都是完全平方数而 3 和 11 不是。
思路
本题从如何减小问题规模入手。
首先对拿到的数我们已经知道任意一个比它小的数最少由几个完全平方数组成
因此我们可以先从当前数字中减掉一个完全平方数然后通过dp直接拿到剩下的数的dp值此时这种切分方式得到的答案就是该dp值1
对当前数字能从中减掉的完全平方数可能不止一个因此我们应该把能减的平方数全都试一遍并把所有答案中最小的那个设为当前数字的dp值。
class Solution {
public:int numSquares(int n) {vectorint dp(n 1);dp[0] 0;//填数组for (int k 1; k n; k) {int curMin INT_MAX;//枚举平方根以下的数for (int i 1; i * i k; i) {curMin min(curMin, dp[k - i * i]);}dp[k] curMin 1;}return dp[n];}
};
【零钱兑换】
给你一个整数数组 coins 表示不同面额的硬币以及一个整数 amount 表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额返回 -1 。
你可以认为每种硬币的数量是无限的。
思路
和上一题本质上没有任何区别只要把上一题枚举的“完全平方数”在这题改成“硬币面值”就完事儿了。
class Solution {
public:int coinChange(vectorint coins, int amount) {int n coins.size();sort(coins.begin(), coins.end());if (amount 0)return 0;if (amount coins[0])return -1;vectorint dp(amount 1);dp[0] 0;//依次计算for (int i 1; i amount; i) {int curMin INT_MAX;//记录当前金额能否凑成bool flag false;// calculate dp[i]//枚举比总数小的所有硬币面值for (int j 0; j n 0 i - coins[j]; j) {//如果去掉当前面值以后能凑出来if (dp[i - coins[j]] ! -1) {//记录最少数量curMin min(curMin, dp[i - coins[j]] 1);//记录可以凑出flag true;}}dp[i] flag ? curMin : -1;}return dp[amount];}
};
