编程笔记

c-计蒜客 跳跃游戏二(动态规划)

11/27/2021 10:13:16 AM
0

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

能采用动态规划求解的问题的一般要具有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],那么通过此主要是想要说明动态规划的特点就是减少重复的计算,利用已算出的值来进行下一步的计算和有重复的子问题。

友情链接

Copyright @2021-2024 关于