动态规划
****************[](https://programmercarl.com/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html)****动态规划五部曲
题目笔记
不同路径
创建dp数组时可以多创建一行和一列，用来防止 dp[i-1][j] + dp[i][j - 1]无效
dp[i][j] 的含义为到达第i行第j列有 dp[i][j] 种方法，遍历即可得答案
java
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int [m + 1][n + 1];
dp[0][1] = 1;
for(int i = 1; i < m + 1; i++ ){
for(int j = 1; j < n + 1; j++){
dp[i][j] = dp[i-1][j] + dp[i][j - 1];
}
}
return dp[m][n];
}
}状态压缩：
在二维dp数组中，当前值的计算只依赖正上方和正左方，因此可以压缩成一维数组。
因为遍历时j是递增的，所以遍历到dp[j]（即当前位置）时dp[j]还没有被修改，而还没有被修改的dp[j]表示的是上一层的到达j位置的种数即dp[i - 1][j]，而由于j是递增的，所以dp[j - 1]是已经被修改过的，表示的是本层的j-1的种数，所以可以直接使用dp[j] += dp[j - 1]，表示当前位置的种数
java
class Solution {
public int uniquePaths(int m, int n) {
// 在二维dp数组中，当前值的计算只依赖正上方和正左方，因此可以压缩成一维数组。
int[] dp = new int[n];
// 初始化，第一行只能从正左方跳过来，所以只有一条路径。
Arrays.fill(dp, 1);
for (int i = 1; i < m; i ++) {
// 第一列也只有一条路，不用迭代，所以从第二列开始
for (int j = 1; j < n; j ++) {
dp[j] += dp[j - 1]; // dp[j] = dp[j] (正上方)+ dp[j - 1] (正左方)
}
}
return dp[n - 1];
}
}整数拆分
dfs（会超时）
java
class Solution {
public int integerBreak(int n) {
if(n <= 2){
return 1;
}
return dfs(n);
}
public int dfs(int n){
if(n <= 2){ //能进入递归的一定是能够被拆分的，所以这里返回的是n而不是1（贪心），就
//是说不不用在考虑这个数组一定要拆分一次
return n;
}
int res = 0;
for(int i = 1; i <= n / 2;i++){
res = Integer.max(res,Integer.max(i * (n - i),i * dfs(n - i)));
}
return res;
}
}dp
java
class Solution {
public int integerBreak(int n) {
int[] dp = new int[n + 1];
dp[2] = 1;
for(int i = 3; i < n + 1; i++){
int sum = 0;
for(int j = 1;j <= i/2;j++){
sum = Integer.max(sum,Integer.max(j * (i - j),j * dp[i - j]));
}
dp[i] = sum;
}
return dp[n];
}
}分割等和子集（01背包问题）
根本想不到
最后一块石头的质量（01背包问题）
1049. 最后一块石头的重量 II - 力扣（LeetCode）
动态规划求解组合问题
dp[j] += dp[j - nums[i]];
目标和
这题相比于01背包求解最大能装多少价值的物品有所不同，这题要求我们求解的是<font style="color:rgba(38, 38, 38, 0.75);">target</font>
所以我们得到dp[i][j] 的方式有两种：
java
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for(int i : nums){
sum+=i;
}
if(Math.abs(target) > sum){
return 0;
}
if((sum + target) % 2 == 1){
return 0;
}
int left = (sum + target) / 2;
int[] dp = new int[left+1];
dp[0] = 1;
for(int i = 0; i < nums.length;i++){
for(int j = left;j >= nums[i];j--){
dp[j] += dp[j - nums[i]];
}
}
return dp[left];
}
}零钱兑换II
这题与上题的思路相同，求解的是得到
所以我们也就是要利用组合数的方法来求解这题，即使用公式 dp[j] += dp[j - nums[i]] 来求解
需要注意的是在使用二维数组时要先初始化第一列和第一行，因为在状态转移方程中当前值需要利用到当前数组的左上角的值
但是在一维数组中，我们只需要初始化 dp[0] = 1,而后面的值初始化为0即可，因为计算店dp[i]的计算公式为
dp[j] += dp[j - nums[i]]，如果将dp[i]初始化其他值的话就会导致dp[i]计算出错
完全背包求组合和排列问题
****
与上题思路相同
这个题不会写，可以直接看灵神笔记