C语言刷题日记 #12026.03.09-03.15本周概览本周主要学习了动态规划的基础题目包括斐波那契数列、爬楼梯、泰波那契数、使用最小花费爬楼梯、打家劫舍等。通过这些题目初步理解了动态规划的状态定义和转移方程也暴露了一些代码实现上的问题。题目复盘1. 509. 斐波那契数我的代码intfib(intn){inta0,b1,c,i;if(n2)returnn;for(i2;in;i){cab;ab;bc;}returnc;}思路使用滚动数组迭代计算。不足之处变量命名不够清晰a,b,c没有注释边界条件处理还可以更简洁。官方解法动态规划同样使用滚动数组但代码更清晰intfib(intn){if(n2)returnn;intp0,q0,r1;for(inti2;in;i){pq;qr;rpq;}returnr;}收获理解了滚动数组的精髓官方代码的变量命名p,q,r更直观表示前两项和当前项。2. 70. 爬楼梯我的代码intclimbStairs(intn){inta0,b1,c,i;for(i1;in;i){cab;ab;bc;}returnc;}思路斐波那契数列应用f(n)f(n-1)f(n-2)用滚动数组。不足之处与斐波那契类似命名可以改进且没有处理n0的情况但题目n≥1。官方解法同样用滚动数组但边界条件明确intclimbStairs(intn){intp0,q0,r1;for(inti1;in;i){pq;qr;rpq;}returnr;}收获理解了爬楼梯的本质就是斐波那契滚动数组写法一致。3. 1137. 第 N 个泰波那契数我的代码inttribonacci(intn){inta0,b1,c1,d,i;if(n2)returnn;if(n3)return2;for(i3;in;i){dabc;ab;bc;cd;}returnc;}思路手动处理边界然后循环。不足之处对n3的特殊处理其实可以合并到循环中代码冗余。官方解法统一用滚动数组从3开始inttribonacci(intn){if(n0)return0;if(n2)return1;intp0,q0,r1,s1;for(inti3;in;i){pq;qr;rs;spqr;}returns;}收获滚动数组可以推广到三项依赖命名规范使逻辑更清晰。4. 746. 使用最小花费爬楼梯我的代码intminCostClimbingStairs(int*cost,intcostSize){inti,record[costSize1];record[0]cost[0];record[1]cost[1];for(i2;icostSize;i)record[i]record[i-2]record[i-1]?record[i-1]cost[i]:record[i-2]cost[i];returnrecord[i-1]record[i-2]?record[i-2]:record[i-1];}思路试图用record[i]表示到达第i阶的最小花费但初始值设为了cost[0]和cost[1]这实际上是把“踏上”第i阶的花费算进去了而题目要求的是到达楼顶第n阶的最小花费且可以选择从0或1开始开始时不花费。不足之处状态定义错误应该用dp[i]表示到达第i阶的最小花费且dp[0]dp[1]0因为可以从0或1开始不花钱。没有考虑最终到达楼顶下标n的情况数组只计算到costSize-1。最后返回的是record[costSize-1]和record[costSize-2]的最小值但正确结果应该是dp[costSize]到达楼顶。官方解法正确动态规划dp[i] min(dp[i-1]cost[i-1], dp[i-2]cost[i-2])dp[0]dp[1]0。intminCostClimbingStairs(int*cost,intcostSize){intprev0,curr0;for(inti2;icostSize;i){intnext(currcost[i-1]prevcost[i-2])?currcost[i-1]:prevcost[i-2];prevcurr;currnext;}returncurr;}收获动态规划的关键是正确设计状态和转移方程特别是初始条件的确定。这道题让我意识到不能想当然地赋值必须严格依据题意。5. 198. 打家劫舍我的代码intbill1;voidelsebill(int*nums,intnumsSize,inti,intbill){intj;for(ji;jnumsSize-4;j2){if(nums[j]nums[j2]nums[j1]nums[j3]nums[j]nums[j1])elsebill(nums,numsSize,j3,billnums[j1]);billnums[j];}if(jnumsSize-1)billnums[j];elseif(jnumsSize-2)bill(nums[j]nums[j1]?nums[j]:nums[j1]);elsebill(nums[j]nums[j2]nums[j1]?nums[j]nums[j2]:nums[j1]);if(billbill1)bill1bill;}introb(int*nums,intnumsSize){bill10;elsebill(nums,numsSize,0,0);returnbill1;}思路试图用递归枚举所有可能的抢劫方案但逻辑复杂且有很多硬编码的条件如jnumsSize-4显然没有抓住问题的本质。不足之处算法复杂且难以理解容易出错。没有利用动态规划的思想导致代码冗长且效率低。全局变量使用不当。官方解法经典动态规划dp[i] max(dp[i-2]nums[i], dp[i-1])空间优化。introb(int*nums,intnumsSize){if(numsSize0)return0;if(numsSize1)returnnums[0];intfirstnums[0],second(nums[0]nums[1])?nums[0]:nums[1];for(inti2;inumsSize;i){inttempsecond;second(firstnums[i]second)?firstnums[i]:second;firsttemp;}returnsecond;}收获打家劫舍是典型的线性动态规划状态转移非常简洁。我的递归枚举方法不仅复杂而且可能遗漏情况。以后遇到类似问题应先思考动态规划而不是盲目枚举。本周总结通过本周的练习我初步掌握了动态规划的基本思想定义状态、写出转移方程、确定边界条件。在实现中我发现了自己的一些问题状态定义有时不准确导致结果错误如746题。代码风格需要改进变量命名要有意义增加注释。遇到复杂问题如198题应先思考动态规划而不是用递归暴力枚举。下周计划继续动态规划专题重点练习一维dp的变种并尝试用滚动数组优化空间。同时要坚持每周参加LeetCode周赛检验学习效果。附本周所有代码已上传至我的GitHub仓库LeetCode-C-Practice