天河网站建设平台湖南智能网站建设报价

天河网站建设平台,湖南智能网站建设报价,wordpress 用户密码的加密算法,贵阳市房地产交易平台上线本周主要对动态规划进行了初步的学习并在力扣上进行了练习内容我认为动态规划有两大要点1.找到相应的递推公式。 2.找到i#xff0c;j#xff0c;dp[i][j]的含义。 在其中有 63.不同路径IIint** inidp(int n, int m, int** obstacleGrid){int** dp (int**)malloc(m * sizeof…本周主要对动态规划进行了初步的学习并在力扣上进行了练习内容我认为动态规划有两大要点1.找到相应的递推公式。2.找到ijdp[i][j]的含义。在其中有63.不同路径IIint** 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背包问题二维#includestdio.h #includestdlib.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]个位置因此要m1. } //全部初始化为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背包问题一维#includestdio.h #includestdlib.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[m1][n1]; memset(dp,0,sizeof(int) * (n1) * (m1)); 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数组的含义和递推公式总结动态规划的内容很多我现在只能对其部分进行应用