二维动态规划 64.最小路径和 intmin(inta,intb){ returna>b?b:a; } //从(0,0)到(i,j)的最小路径和，只能向右或向下移动 intrecursive(intgrid,inti,intj){ if(i0&&j0)returngrid[0][0]; intup=0x7fffffff; intleft=0x7fffffff; if(i1>=0)up=recursive(grid,i1,j); if(j1>=0)left=recursive(grid,i,j1); //只能从上方或者左侧到当前位置，选则更小的路径和 retu...

二维动态规划（下） 115.不同的子序列 //自底向上 intnumDistinct(chars,chart){ constintMOD=1e9+7; intlenS=strlen(s); intlenT=strlen(t); //dp[i][j]表示在s中前缀长度为i的字符串所包含的所有子序列中，有多少个子序列等于t中前缀长度为j的字符串 //i、j表示前缀长度，而不是字符串中的下标 intdp[lenS+1][lenT+1]; //第一列全1，表示空串的时候匹配 for(inti=0;i<=lenS;i)dp[i][0]=1; //第一行除了第一个元素，全0，不可能匹配 for(in...

三维动态规划 474.一和零 多维费用背包 intzeros; intones; intlen; voidcount(chars){ zeros=0; ones=0; intl=strlen(s); for(inti=0;i<l;i){ if(s[i]'0')zeros; if(s[i]'1')ones; } } intmax(inta,intb){ returna>b?a:b; } //返回0不超过z，1不超过o时，strs从curIndex下标往后选，最大的子集长度 intrecursive(charstrs,intcurIndex,intz,into){ if(cu...

子数组最大累加和 53.最大子数组和 返回子数组最大累加和 返回子数组的开始和结束位置 intmax(inta,intb,intc){ intd=a>b?a:b; returnd>c?d:c; } //必须经过mid和mid+1 intmaxCrossingSum(intnums,intleft,intmid,intright){ intleftMax=nums[mid]; intrightMax=nums[mid+1]; intindex=mid; inttempMax=0; //找左边以mid结尾的最大连续子数组的和 while(index>=left){ tem...

构建前缀信息 303.区域和检索数组不可变 构建前缀和数组，快速计算子数组区间和 classNumArray{ publicint[]prefixSum; publicNumArray(int[]nums){ prefixSum=newint[nums.length+1]; //计算前缀和 for(inti=1;i<=nums.length;i) prefixSum[i]=prefixSum[i1]+nums[i1]; } publicintsumRange(intleft,intright){ returnprefixSum[right+1]prefixSum[left]; }...

滑动窗口 209.长度最小的子数组 intmin(inta,intb){ returna>b?b:a; } intminSubArrayLen(inttarget,intnums,intnumsSize){ intres=0x7fffffff; for(intl=0,r=0,sum=0;r<numsSize;r){ //查看以nums[r]结尾的子数组中是否有符合条件的 sum+=nums[r]; //尽量减小以nums[r]结尾的子数组长度 while(sumnums[l]>=target){ sum-=nums[l]; l; } //记录所有位置结尾中的最短数组 if(...

单调队列 239.滑动窗口最大值 intmaxSlidingWindow(intnums,intnumsSize,intk,intreturnSize){ returnSize=numsSizek+1; intres=(int)malloc(sizeof(int)(returnSize)); //双端队列，从大到小排，记录在nums中的下标 intdequeue[100001]; intfront=0,rear=0; //先把窗口扩大到k-1 for(inti=0;i<k1;i){ //小于等于nums[i]的全部从队尾出队 while(front<rear&&n...

一维动态规划 509.斐波那契数 intdp; //自顶向下记忆化搜索，时间复杂度O（n） intrecursive(intn){ if(n0)return0; if(n1)return1; //若之前计算过就直接返回 if(dp[n]!=-1)returndp[n]; dp[n]=recursive(n2)+recursive(n1); returndp[n]; } intfib(intn){ dp=(int)malloc(sizeof(int)(n+1)); memset(dp,-1,sizeof(int)(n+1)); returnrecursive(n); } //自下而上，时间...