LeetCode 第45天 | 57. 爬楼梯 322. 零钱兑换 518. 零钱兑换II 279. 完全平方数 动态规划

57. ���楼梯（第八期模拟笔试）

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬至多m (1 int n,m; cinn>m; std::vector dp(n+1,0); dp[0] = 1; for (int i = 1; i for (int j = 1; j // 向前找m个位置，各个位置都可以到达i，因此累加前面的结果 if (i-j = 0) dp[i] += dp[i-j]; } } coutpublic: int coinChange(vector // 定义数组，大小为背包容量金额amount， 初始化为最大值，因为后面要去最小值 vector for (int j = coins[i]; j if (dp[j - coins[i]] != INT_MAX) { // 如果前面的没有初始化过，则跳过 dp[j] = min(dp[j], dp[j-coins[i]]+1); } } } // 如果最后没有到达右下角的结果，返回-1 if (dp[amount] == INT_MAX) return -1; return dp[amount]; }};public: int change(int amount, vector vector for (int j = coins[i]; j // dp[j]表示j容量填满有多少种方法 dp[j] += dp[j-coins[i]]; } } return dp[amount]; }};public: int numSquares(int n) { // 容量为n，想要装填满n vector // j的大小从i开始，寻找完全平方数，某些不是完平方的被INT_MAX屏蔽了 for (int j = i*i; j dp[j] = min(dp[j], dp[j-i*i] + 1); } } return dp[n]; }};