資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C語言程式：到達終點的最小跳躍次數
給定一個非負整數陣列，表示從該元素可以向前跳躍的最大步數。指標最初位於陣列的第一個索引[0索引]。目標是以最少的步數到達陣列的最後一個索引。如果無法到達陣列的末尾，則列印最大整數。
樸素方法是從初始（主要）元素開始，遞迴呼叫所有可從第一個元素訪問的元素。從第一個元素到達末尾的最小跳躍次數是使用從第一個元素可訪問的元素到達末尾所需的最小跳躍次數計算出來的。
minJumps(start, end) = Min ( minJumps(k, end) ) for all k accessible from the start
在這裡，我們將使用動態規劃的自頂向下方法。我們將使用雜湊表來儲存子問題的結果，並且每當我們建立解決方案時，首先檢查子問題是否已經解決，如果是，則使用它。
Input: { 1, 2, 4, 1, 2, 2, 1, 1, 3, 8 }
Output: Minimum number of steps = 6 {1-->2-->4-->1-->3-->8}解釋
第一個元素是1，所以它只能到2。第二個元素是2，所以最多可以跳2步，例如到4或1。它從4跳到1，依此類推。
使用動態規劃方法查詢到達陣列末尾的最小跳躍次數的複雜度為O(n^2)，空間複雜度為O(n)。
示例
#include<stdio.h>
#include<limits.h>
int min_steps (int arr[], int n){
int steps[n];
int i, j;
if (n == 0 || arr[0] == 0)
return INT_MAX;
steps[0] = 0;
for (i = 1; i < n; i++){
steps[i] = INT_MAX;
for (j = 0; j < i; j++){
if (i <= j + arr[j] && steps[j] != INT_MAX){
steps[i] = (steps[i] < (steps[j] + 1)) ? steps[i] : steps[j] + 1;
break;
}
}
}
return steps[n - 1];
}
int main (){
int arr[100];
int n;
printf ("Enter size of the array:");
scanf ("%d", &n);
printf ("Enter elements in the array:");
for (int i = 0; i < n; i++){
scanf ("%d", &arr[i]);
}
printf ("Minimum number of steps : %d", min_steps (arr, n));
return 0;
}輸出
Enter size of array : 7 Enter elements in the array :2 1 1 5 2 1 1 Minimum number of steps : 3
更新於：2019年12月24日
567 次瀏覽
廣告