如何用C语言解决一个经典的动态规划问题：数组跳跃游戏

学习工控知识，就来工控小新

农历十一月初五

2023/12/ 17

往期推荐

2023年12月16日，这个C语言的编程题目，可能是你见过的最简单的矩阵运算！

2023年12月14日，每天花费一分钟练习C语言：用C语言判断自己体重标准，今天你瘦了吗？

每日一练

/ Daily Exercises

题目：

给定一个非负整数数组nums ，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。

题目分析

这是一个经典的动态规划问题，它要求给定一个非负整数数组nums，判断从数组的第一个下标开始，是否能够通过跳跃到达最后一个下标。数组中的每个元素代表在该位置可以跳跃的最大长度。例如，给定数组 [2, 3, 1, 1, 4]，从第一个下标开始，可以跳跃到第二个下标，然后跳跃到第四个下标，再跳跃到最后一个下标，所以返回true。但是，给定数组 [3, 2, 1, 0, 4]，从第一个下标开始，无论如何都无法跳跃到最后一个下标，所以返回false。

要解决这个问题，我们可以使用一个一维数组dp，用来记录从第一个下标开始，能够跳跃到的最远的下标。初始时，dp[0] = nums[0]，表示从第一个下标开始，最多可以跳跃到第一个下标加上第一个元素的位置。然后，我们遍历数组中的每个元素，对于每个元素，我们判断它的下标是否小于等于当前的最远跳跃下标，如果是，说明它是可以到达的，那么我们就更新最远跳跃下标为它的下标加上它的元素值，和原来的最远跳跃下标的较大值。如果不是，说明它是无法到达的，那么我们就跳过它，继续遍历下一个元素。最后，我们判断最远跳跃下标是否大于等于数组的最后一个下标，如果是，说明可以跳跃到最后一个下标，返回true。如果不是，说明无法跳跃到最后一个下标，返回false。

为了实现这个算法，我们需要定义一个函数，用来判断一个数组是否能够跳跃到最后一个下标。函数的参数是一个非负整数数组和它的长度，函数的返回值是一个布尔值，表示是否能够跳跃到最后一个下标。

函数伪代码

// 定义跳跃函数bool canJump(int[] nums, int n) {  // 如果数组为空或者长度为0，返回false  if (nums == null || n == 0)   {    return false;  }  // 定义一个变量，用来记录从第一个下标开始，能够跳跃到的最远的下标，初始值为nums[0]  int maxJump = nums[0];  // 遍历数组中的每个元素，从第二个元素开始  for (int i = 1; i < n; i++)   {    // 判断当前元素的下标是否小于等于最远跳跃下标，如果是，说明它是可以到达的    if (i <= maxJump)   {      // 更新最远跳跃下标为当前元素的下标加上当前元素的值，和原来的最远跳跃下标的较大值      maxJump = max(maxJump, i + nums[i]);      // 如果最远跳跃下标已经大于等于数组的最后一个下标，说明可以跳跃到最后一个下标，返回true      if (maxJump >= n - 1)    {        return true;      }    }    // 如果当前元素的下标大于最远跳跃下标，说明它是无法到达的，跳过它，继续遍历下一个元素    else   {      continue;    }  }  // 遍历完所有的元素后，如果最远跳跃下标仍然小于数组的最后一个下标，说明无法跳跃到最后一个下标，返回false  return false;}

完整程序展示

// 导入标准输入输出库#include <stdio.h>// 定义一个辅助函数，用来求两个整数的较大值int max(int a, int b) {  return a > b ? a : b;}// 定义跳跃函数，参数和返回值与伪代码相同bool canJump(int nums[], int n) {  if (nums == NULL || n == 0)   {    return false;  }  int maxJump = nums[0];  for (int i = 1; i < n; i++)   {    if (i <= maxJump)     {      maxJump = max(maxJump, i + nums[i]);      if (maxJump >= n - 1)       {        return true;      }    }    else     {      continue;    }  }  return false;}// 定义主函数，用来测试跳跃函数int main() {  // 定义两个测试用例的数组和它们的长度  int nums1[5] = {2, 3, 1, 1, 4};  int n1 = 5;  int nums2[5] = {3, 2, 1, 0, 4};  int n2 = 5;  // 调用跳跃函数，传入数组和长度，打印返回值  printf("The result for the first array is %d.\n", canJump(nums1, n1));  printf("The result for the second array is %d.\n", canJump(nums2, n2));  // 返回0，表示程序正常结束  return 0;}

程序测试

运行程序：

下期题目

给定一个二叉树，检查它是不是镜像对称的