【Lcode 随笔】C语言版看了不后悔系列持续更新中。。。

在这里插入图片描述

文章目录

- 题目一：爬楼梯
- - 问题描述：
  - 题目分析：
  - 解题思路：
  - 示例代码：
  - 深入剖析：
- 题目二：打家劫舍
- - 问题描述：
  - 题目分析：
  - 解题思路：
  - 示例代码：
  - 深入剖析：
- 题目三：最小路径和
- - 问题描述：
  - 题目分析：
  - 解题思路：
  - 示例代码：
  - 深入剖析：

🌈你好呀！我是山顶风景独好
🎈欢迎踏入我的博客世界，能与您在此邂逅，真是缘分使然！😊
🌸愿您在此停留的每一刻，都沐浴在轻松愉悦的氛围中。
📖这里不仅有丰富的知识和趣味横生的内容等您来探索，更是一个自由交流的平台，期待您留下独特的思考与见解。🌟
🚀让我们一起踏上这段探索与成长的旅程，携手挖掘更多可能，共同进步！💪✨

题目一：爬楼梯

问题描述：

假设你正在爬楼梯。需要 n 步你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

题目分析：

这个问题是一个典型的动态规划问题。我们可以定义一个数组 dp，其中 dp[i] 表示到达第 i 个台阶的方法数。根据题目要求，到达第 i 个台阶可以从第 i-1 个台阶爬 1 步上来，也可以从第 i-2 个台阶爬 2 步上来。因此，状态转移方程为 dp[i] = dp[i-1] + dp[i-2]。同时，我们需要初始化 dp[0] = 1（表示在起点，方法数为 1），dp[1] = 1（表示第一步可以直接爬 1 步上来）。

解题思路：

初始化 dp 数组，dp[0] = 1, dp[1] = 1。
使用循环从 2 到 n 遍历，根据状态转移方程计算 dp[i]。
返回 dp[n]，即到达楼顶的方法数。

示例代码：

#include <stdio.h>  int climbStairs(int n) {  if (n <= 1) return 1;  int dp[n + 1];  dp[0] = 1;  dp[1] = 1;  for (int i = 2; i <= n; i++) {  dp[i] = dp[i - 1] + dp[i - 2];  }  return dp[n];  
}  int main() {  int n = 5;  printf("到达楼顶的方法数为: %d\n", climbStairs(n));  return 0;  
}

深入剖析：

这个问题展示了动态规划在解决重复子问题方面的优势。通过存储已经计算过的结果，避免了重复计算，从而提高了算法的效率。此外，这个问题也体现了递归和动态规划之间的区别，即动态规划通过自底向上的方式解决问题，避免了递归可能导致的栈溢出问题。

题目二：打家劫舍

问题描述：

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

题目分析：

这个问题同样是一个动态规划问题。我们可以定义一个数组 dp，其中 dp[i] 表示偷到第 i 个房屋时能够得到的最高金额。由于不能偷相邻的房屋，所以对于第 i 个房屋，我们有两种选择：偷或不偷。如果我们选择偷第 i 个房屋，那么就不能偷第 i-1 个房屋，此时 dp[i] = dp[i-2] + nums[i]（nums 是存放金额的数组）。如果我们选择不偷第 i 个房屋，那么 dp[i] = dp[i-1]。因此，状态转移方程为 dp[i] = max(dp[i-1], dp[i-2] + nums[i])。

解题思路：

初始化 dp 数组，dp[0] = nums[0]（只偷第一个房屋），dp[1] = max(nums[0], nums[1])（偷第一个或第二个房屋）。
使用循环从 2 到 n 遍历，根据状态转移方程计算 dp[i]。
返回 dp[n]，即能够偷窃到的最高金额。

示例代码：

#include <stdio.h>  int rob(int* nums, int numsSize) {  if (numsSize == 0) return 0;  if (numsSize == 1) return nums[0];  int dp[numsSize];  dp[0] = nums[0];  dp[1] = (nums[0] > nums[1]) ? nums[0] : nums[1];  for (int i = 2; i < numsSize; i++) {  dp[i] = (dp[i - 1] > (dp[i - 2] + nums[i])) ? dp[i - 1] : (dp[i - 2] + nums[i]);  }  return dp[numsSize - 1];  
}  int main() {  int nums[] = {1, 2, 3, 1};  int numsSize = sizeof(nums) / sizeof(nums[0]);  printf("能够偷窃到的最高金额为: %d\n", rob(nums, numsSize));  return 0;  
}

深入剖析：

这个问题展示了动态规划在解决选择最优解问题时的强大能力。通过定义状态转移方程，我们可以将问题分解为更小的子问题，并逐一解决。同时，这个问题也提醒我们，在定义状态转移方程时，需要仔细考虑所有可能的情况，确保不漏掉任何一种选择。

题目三：最小路径和

问题描述：

给定一个 m x n 的网格和一个整数。网格中的每个格子都有一个整数。现在你需要从左上角，走到右下角。每次只能向右或者向下移动一步。在网格中只能访问每个格子一次。找出从左上角到右下角的最小路径和。

题目分析：

这个问题同样是一个动态规划问题。我们可以定义一个二维数组 dp，其中 dp[i][j] 表示到达网格中第 i 行第 j 列格子时的最小路径和。由于每次只能向右或向下移动，所以对于第 i 行第 j 列的格子，我们可以从它左边的格子 dp[i][j-1] 或上边的格子 dp[i-1][j] 移动过来。因此，状态转移方程为 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]（grid 是存放网格中整数的二维数组）。

解题思路：

初始化 dp 数组的第一行和第一列，它们分别表示从左上角到第一行或第一列每个格子的最小路径和。
使用两个嵌套的循环遍历网格中的每个格子，根据状态转移方程计算 dp[i][j]。
返回 dp[m-1][n-1]，即从左上角到右下角的最小路径和。

示例代码：

#include <stdio.h>  
#include <limits.h>  int minPathSum(int** grid, int gridSize, int* gridColSize) {  int m = gridSize;  int n = gridColSize[0];  int dp[m][n];  // 初始化第一行和第一列  dp[0][0] = grid[0][0];  for (int i = 1; i < m; i++) {  dp[i][0] = dp[i-1][0] + grid[i][0];  }  for (int j = 1; j < n; j++) {  dp[0][j] = dp[0][j-1] + grid[0][j];  }  // 填充 dp 数组  for (int i = 1; i < m; i++) {  for (int j = 1; j < n; j++) {  dp[i][j] = (dp[i-1][j] < dp[i][j-1]) ? dp[i-1][j] : dp[i][j-1] + grid[i][j];  }  }  return dp[m-1][n-1];  
}  int main() {  int grid[2][3] = {{1, 3, 1}, {1, 5, 1}};  int gridSize = 2;  int gridColSize[2] = {3, 3};  int** gridPtr = (int**)malloc(gridSize * sizeof(int*));  for (int i = 0; i < gridSize; i++) {  gridPtr[i] = grid[i];  }  printf("从左上角到右下角的最小路径和为: %d\n", minPathSum(gridPtr, gridSize, gridColSize));  free(gridPtr);  return 0;  
}