【算法练习】leetcode算法题合集之动态规划篇
普通动规系列
LeetCode343. 整数拆分
LeetCode343. 整数拆分
将10的结果存在索引为10的位置上，需要保证数组长度是
n+1，索引的最大值是n，索引是从0开始的。n的拆分，可以拆分为
i和n-i，当然i可以继续拆分。而且拆分为n-1和1的结果和n-2和2的结果的大小也是不一定的。
class Solution {public int integerBreak(int n) {int[] dp = new int[n + 1];for (int i = 2; i <= n; i++) {int max = 0;for (int j = 1; j < i; j++) {max = Math.max(max, Math.max(dp[i - j] * j, (i - j) * j));}dp[i] = max;}return dp[n];}
}
LeetCode70. 爬楼梯（⭐️Hot100 腾讯）
LeetCode70. 爬楼梯
需要考虑n==1的情况。
class Solution {public int climbStairs(int n) {int[] dp = new int[n + 1];dp[1] = 1;dp[0] = 1;for (int i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
}
