本周主要对动态规划进行了初步的学习并在力扣上进行了练习
内容
我认为动态规划有两大要点
1.找到相应的递推公式。
2.找到i，j，dp[i][j]的含义。
在其中有
63.不同路径II
int** inidp(int n, int m, int** obstacleGrid){ int** dp = (int**)malloc(m * sizeof(int*)); for(int i = 0;i < m;i++){ dp[i] = (int*)malloc(n * sizeof(int)); } for(int i = 0;i < m;i++){ dp[i][0] = 0; } for(int i = 0;i < n;i++){ dp[0][i] = 0; } for(int i = 0;i < m;i++){ if(obstacleGrid[i][0])break; dp[i][0] = 1; } for(int i = 0;i < n;i++){ if(obstacleGrid[0][i])break; dp[0][i] = 1; } return dp; } int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize) { int n = *obstacleGridColSize; int m = obstacleGridSize; if(obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1)return 0; int** dp = inidp(n,m,obstacleGrid); for(int i = 1;i < m;i++){ for(int j = 1;j < n;j++){ if(obstacleGrid[i][j]){ dp[i][j] = 0; continue; } dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } return dp[m - 1][n - 1]; }
是典型的应用
在这其中明白障碍点的路径数为0，第一行列的路径数为1（若障碍在第一行列时，自障碍以后的全是0）
到达非第一行列的路径是其上面的路径数 + 左边的路径数。
其中i代表的是行，j代表列，dp[i][j]代表该点的路径数
便大概可以做出本题
01背包问题（二维）
#include<stdio.h> #include<stdlib.h> int max(int a, int b){ return (a > b)?a:b; } int main(){ int n, m, i, j; scanf("%d %d",&n,&m);//n 为物品数量 ， m 为背包容量 。 int a[n], b[n]; for(i = 0;i < n;i++){ scanf("%d",&a[i]); } for(i = 0;i < n;i++){ scanf("%d",&b[i]); } int** dp = (int**)malloc(n * sizeof(int*)); for(i = 0;i < n;i++){ dp[i] = (int*)malloc((m + 1) * sizeof(int));//因为有 背包容量为 m 则会有[0—m]个位置，因此要m+1. } //全部初始化为0 。 for(i = 0;i < n;i++){ for(j = 0;j <= m;j++){ dp[i][j] = 0; } } //将第一个物品所代表的行填满，当背包容量j > 物品质量a[0]时，将第一个物品的价值填入。 for(j = 0;j <= m;j++){ if(j >= a[0]) dp[0][j] = b[0]; } for(i = 1;i < n;i++){ for(j = 0;j <= m;j++){ if(j < a[i])dp[i][j] = dp[i - 1][j];//若当前物品质量>背包容量则将上一个物品的价值填入（若上一个也不满足则会继续往上，倘若没有合适的则会为0） else{ //若当前物品质量<背包容量则会将会为 上一个物品的价值 和 当前物品的价值 + 上一个物品在背包容量为 （当前背包容量 - 当前物品质量时的价值 的最大值。 dp[i][j] = max(dp[i-1][j],dp[i - 1][j - a[i]] + b[i]); } } } printf("%d",dp[n - 1][m]); return 0; }
其要点在注释中已写
背包问题的的递推公式为dp[i-1][j],dp[i - 1][j - a[i]] + b[i]。
01背包问题（一维）
#include<stdio.h> #include<stdlib.h> int max(int a,int b){ return (a > b)? a : b; } int main(){ int n, m, i, j; scanf("%d %d",&n,&m); int a[n], v[n]; for(i = 0;i < n;i++){ scanf("%d",&a[i]); } for(i = 0;i < n;i++){ scanf("%d",&v[i]); } int* dp = (int*)malloc((m + 1) * sizeof(int)); for(i = 0;i <= m;i++){ dp[i] = 0; } for(i = 0;i <= m;i++){ if(i >= a[0]){ dp[i] = v[0]; } } for(i = 1;i < n;i++){ for(j = 0;j <= m;j++){ if(j < a[i]); else{ dp[j] = max(dp[j],dp[j - a[i]] + v[i]); } } } printf("%d",dp[m]); return 0; }相比于二维而言一维的差异在递推公式
dp[j] = max(dp[j],dp[j - a[i]] + v[i]）
其中01背包的类型我目前见过三种
1.返回正误
416.分割等和子集
int max(int a, int b){ return (a > b)? a : b; } bool canPartition(int* nums, int numsSize) { int sum = 0; for(int i = 0;i < numsSize;i++){ sum += nums[i]; } if(sum % 2){ return false; } int mid = sum / 2; int* dp = (int*)malloc((mid + 1) * sizeof(int)); for(int i = 0;i <= mid;i++){ dp[i] = 0; } for(int i = 0;i <= mid;i++){ if(i >= nums[0]){ dp[i] = nums[0]; } } for(int i = 1;i < numsSize;i++){ for(int j = mid;j > nums[i];j--){ if(j < nums[i]); else{ dp[j] = max(dp[j],dp[j - nums[i]] + nums[i]); } } } return dp[mid] == mid; }2.返回数
int max(int a, int b){ return (a > b)? a : b; } int lastStoneWeightII(int* stones, int stonesSize) { int sum = 0; for(int i = 0;i < stonesSize;i++){ sum += stones[i]; } int mid = sum / 2; int* dp = (int*)calloc((mid + 1) , sizeof(int)); for(int i = 0;i <= mid ; i++){ if(i >= stones[0]){ dp[i] = stones[0]; } } for(int i = 1;i < stonesSize;i++){ for(int j = mid;j >= stones[i];j--){ if(j >= stones[i]){ dp[j] = max(dp[j],dp[j - stones[i]] + stones[i]); } } } int n = sum - 2 * dp[mid]; return n; }3.返回数组数
int max(int a, int b){ return (a > b)? a : b; } int findMaxForm(char** strs, int strsSize, int m, int n) { int dp[m+1][n+1]; memset(dp,0,sizeof(int) * (n+1) * (m+1)); for(int k = 0;k < strsSize;k++){ int n1 = 0; int n0 = 0; char* str = strs[k]; while(*str != '\0'){ if(*str == '0'){ n0++; }else{ n1++; } str++; } for(int i = m;i >= n0;i--){ for(int j = n;j >= n1;j--){ dp[i][j] = max(dp[i][j],dp[i - n0][j - n1] + 1); } } } return dp[m][n]; }这三种的应用主要是在于对题目的理解
以及dp数组的含义和递推公式
总结
动态规划的内容很多，我现在只能对其部分进行应用
