【算法练习】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];}
}