c-计蒜客 跳跃游戏二（动态规划）

浏览量 1

这里借这道题目了解一下动态规划的相关算法。说到动态规划，最简单和熟悉的例子就是斐波拉切数列，这里就不做讲解了，如果不是很熟悉，可自行搜索研究一下。

能采用动态规划求解的问题的一般要具有3个性质： (1) 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。 (2) 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。 (3)有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。(该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势)这里可以查看 红脸书生 的这篇博客有讲解，还有包括算法的框架。 下面给出题目的代码（来自小雨滔滔的博客代码）

#include <stdio.h>
#include <string.h>
#define min(a,b) ((a)<(b)?(a):(b))
int main(){
    int n;
    scanf("%d",&n);
    int a[n],dp[n];
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    dp[n-1]=0;
    for(int i=n-2;i>=0;i--){
        dp[i]=n;
        for(int j=i;j<n&&j<=i+a[i];j++){
            dp[i]=min(dp[i],dp[j]+1);
        }//dp[i]代表从i到n-1所需的最小步数
    }
    printf("%d",dp[0]);
    return 0;
}

以示例(3 1 1 1 1)输入来来分析一下: 其中dp[i]表示的是第i个元素到最后一个元素，所需要的最少次数，我们先从最后一个数开始递推(n=5) 当i=4，dp[4]=0，a[4]到a[4]就是0。 当i=3，dp[3]=1，a[3]到a[4]就是1。 当i=2，dp[2]=2，当i=1，dp[1]=3。 当i=0，dp[0]=2，这里就要看关于j的循环了，i从零开始循环到3，从第一个数最远能跳3格，在计算中就使用了刚才所算出来了得，dp[3],dp[2]和dp[1],那么通过此主要是想要说明动态规划的特点就是减少重复的计算，利用已算出的值来进行下一步的计算和有重复的子问题。