Faits :
A.
A.a. L'art. 8 let. c de la loi [du canton du Valais] du 20 janvier 1953 sur la police cantonale (RS/VS 550.1) donne au Conseil d'Etat la compétence de fixer par ordonnance le traitement, le logement, les indemnités et les congés. Se fondant sur cette délégation, le Conseil d'Etat a adopté l'ordonnance du 20 décembre 1995 concernant le traitement des membres du corps de la police cantonale (OTMPC; RS/VS 550.110). L'art. 3 al. 1 de cette ordonnance dispose que le traitement de base est fixé dans le cadre de l'échelle des traitements de l'administration cantonale. L'art. 12 al. 4 OTMPC a la teneur suivante:
"Pour le policier nouvellement nommé qui bénéficie d'une expérience professionnelle ou autre déjà acquise, le Conseil d'Etat fixe l'augmentation initiale, compte tenu de la nature et de la durée de l'activité antérieure."
L'échelle des traitements de l'année 2000 de l'administration cantonale, établie par le Département cantonal des finances, prévoyait à ce propos que l'activité antérieure d'un nouveau collaborateur était prise en considération de la manière suivante:
- activité antérieure identique ou analogue: 2 % par an;
- activité antérieure partiellement comparable: 1 % par an;
- activité antérieure sans rapport: 0, 5 % par an.
A cette époque et selon cette échelle des traitements, un système dit de paliers d'attente était en vigueur pour des raisons financières. Il s'agissait d'une réduction du traitement défini alors selon deux paliers, de 6 % (classes de salaire A1 à 21; premier palier) et de 4 % (classes de salaire 22 à 26; deuxième palier).
A.b. A._, née en _, a été nommée au grade de gendarme par le Conseil d'Etat du Valais, tout d'abord à titre provisoire en 1999, puis à titre définitif en 2000. Lors de sa nomination, elle a été colloquée en classe 18 et soumise à un palier d'attente de 6 %. Il n'a pas été tenu compte de son activité antérieure d'employée de bureau (parts d'expérience).
Au cours de sa carrière au sein de la police, A._ a été promue successivement aux grades d'appointé, puis de caporal, et enfin de sergent avec effet au 1 er janvier 2013.
A.c. Le 2 juillet 2003, A._, se référant à des "courriers similaires de plusieurs collègues", a demandé au commandant de la police valaisanne la prise en compte dans son traitement initial, sous la forme de parts d'expérience, des quatre années durant lesquelles elle avait travaillé comme employée de commerce entre 1994 et 1998. Le 28 août 2003, cette requête a fait l'objet d'une détermination du service juridique de l'ancien Département des finances, de l'agriculture et des affaires extérieures. Celui-ci l'a considérée comme dénuée de fondement, attendu que la question avait été traitée au moment de l'engagement de l'intéressée et qu'il n'y avait pas lieu d'y revenir plusieurs années plus tard, les conditions d'une révision n'étant au demeurant pas réalisées. Cette détermination a été communiquée à la fonctionnaire le 24 septembre 2003. Celle-ci a par la suite vainement réitéré sa requête, ce qui a conduit le juriste de l'état-major de la police cantonale a confirmer le refus de l'Etat et à "mettre un terme à (la) procédure" (lettre du 23 mai 2007).
Après avoir encore entrepris sans succès diverses démarches, notamment auprès du Président du Conseil d'Etat et de la conseillère d'Etat en charge du Département de la sécurité, des affaires sociales et de l'intégration, A._ a adressé le 28 décembre 2012 une lettre au Conseil d'Etat pour lui faire part de son incompréhension face au refus des autorités, alors même que, selon ses affirmations, une augmentation de traitement avait été accordée à d'autres collaborateurs entrés après elle au service de la police. Elle demandait que son traitement fût augmenté de 4 % avec effet à la date de son engagement. Statuant le 20 février 2013, le Conseil d'Etat a refusé d'entrer en matière au motif qu'une reconsidération heurterait le principe de la sécurité juridique, qu'elle engendrerait des corrections avec effet rétroactif sur plusieurs années du traitement et des cotisations d'assurances sociales, incompatibles avec le principe comptable de l'annualité et, qu'enfin, elle irait à l'encontre de la responsabilisation des membres du personnel de la fonction publique dont on pouvait attendre qu'ils manifestent en temps utile leur désaccord avec leurs conditions salariales.
B.
B.a. Par arrêt du 14 mai 2013, le Tribunal fédéral a déclaré irrecevable le recours formé contre cette décision par A._. Il a considéré que la décision attaquée n'émanait pas d'une autorité judiciaire supérieure. Il a transmis la cause à l'autorité judiciaire qui paraissait normalement compétente, à savoir la Cour de droit public du Tribunal cantonal du canton du Valais (cause 8C_240/2013).
B.b. Saisie du litige à la suite de cet arrêt, la Cour de droit public du Tribunal cantonal valaisan a rejeté le recours en confirmant le refus d'entrer en matière du Conseil d'Etat (jugement du 9 août 2013).
C.
A._ exerce un recours en matière de droit public contre ce jugement, dont elle demande l'annulation. Elle conclut, principalement, au renvoi de la cause à l'autorité précédente. Subsidiairement, elle demande à être mise au bénéfice, avec effet rétroactif sur cinq ans et pour l'avenir, "de l'augmentation initiale à raison de 1 % par an pour 4 ans, soit 4 %".
Le Conseil d'Etat conclut au rejet du recours.

Considérant en droit :
1.
Le litige porte sur une augmentation de traitement dans le domaine de la fonction publique. Il s'agit, par conséquent, d'une contestation pécuniaire, si bien que le motif d'exclusion de l'art. 83 let. g LTF n'entre pas en considération. Il est admis, par ailleurs, que la valeur litigieuse atteint le seuil de 15'000 fr. ouvrant la voie du recours en matière de droit public (art. 51 al. 2 et 85 al. 1 let. b LTF).
2.
Le recours en matière de droit public peut être interjeté pour violation du droit, au sens des art. 95 et 96 LTF. Le Tribunal fédéral applique le droit d'office (<ref-law>). Toutefois, il n'examine que les griefs soulevés, sauf en présence de violations de droit évidentes (<ref-ruling> consid. 2 p. 88; <ref-ruling> consid. 1.6 p. 280). En outre, le Tribunal fédéral ne se prononce sur la violation de droits fondamentaux que s'il se trouve saisi d'un grief motivé de façon détaillée conformément aux exigences accrues de l'<ref-law>. Le recourant doit énoncer le droit ou principe constitutionnel violé et exposer de manière claire et circonstanciée en quoi consiste la violation (cf. <ref-ruling> consid. 1.4 p. 176).
3.
Le Tribunal fédéral conduit par ailleurs son raisonnement juridique sur la base des faits établis par l'autorité précédente (<ref-law>). Il ne peut s'en écarter que si les faits ont été établis de façon manifestement inexacte - ce qui correspond à la notion d'arbitraire (<ref-ruling> consid. 4.1.2 p. 62; <ref-ruling> consid. 5.1 p. 356) - ou en violation du droit au sens de l'<ref-law> (<ref-law>).
4.
Les premiers juges ont confirmé le refus du Conseil d'Etat d'entrer en matière sur la demande de la recourante. Ils ont laissé indécis le point de savoir si les conditions d'engagement de l'intéressée, qui omettaient de tenir compte de ses années d'expérience, étaient ou non irrégulières. En effet, à supposer que tel ait été le cas, l'intérêt public à une application correcte du droit objectif devait céder le pas au principe de la bonne foi qui exigeait que la fonctionnaire examinât d'emblée les conditions de son engagement. A ce propos, la juridiction cantonale retient que la recourante a été personnellement informée, peu de temps après sa nomination, des modalités de calcul de son traitement au moyen d'une fiche de salaire détaillant les parts d'expérience prises en considération (en l'occurrence 0) et le taux de palier d'attente. Le principe de la bonne foi (art. 5 al. 3 Cst.) exigeait qu'elle fît part sans retard d'éventuelles doléances au sujet de ses conditions salariales. Au lieu de cela, elle a laissé s'écouler plusieurs années avant de formuler une requête en juillet 2003. Quant au fait - invoqué par la recourante - que l'un de ses collègues, issu de la même classe d'aspirants, a pu bénéficier, à sa demande, d'une augmentation de son traitement initial en automne 2003, la juridiction cantonale considère que cette circonstance ne permettait pas, dix ans plus tard, d'assimiler la situation de l'intéressée à celle de ce collègue. Au demeurant, ajoutent les premiers juges, le cas de ce fonctionnaire a fait l'objet d'un examen isolé débouchant sur une solution particulière, parce qu'il avait auparavant fait partie d'un autre corps de police; les demandes des autres candidats ont suivi le même sort que celui réservé aux prétentions de la recourante.
5.
Invoquant tout d'abord une constatation manifestement inexacte des faits, la recourante fait grief à la juridiction précédente d'avoir retenu sans autre examen qu'elle avait été personnellement informée, à l'époque de sa nomination, que son traitement n'englobait pas des parts d'expérience. La recourante se prévaut ensuite du droit à l'égalité de traitement par rapport à la situation de son collègue qui a bénéficié en 2003 d'une augmentation rétroactive de son salaire initial. Enfin, elle se plaint d'une application arbitraire de l'art. 12 al. 4 OTMPC. En substance, elle reproche aux premiers juges d'être tombés dans l'arbitraire en opposant à ses prétentions les principes de la sécurité juridique et de la bonne foi.
6.
6.1. Contrairement à la garantie à une rémunération égale de l'homme et de la femme qui confère un droit subjectif en vertu de la réglementation spécifique (art. 8 al. 3 Cst.; loi fédérale du 24 mars 1995 sur l'égalité entre femmes et hommes [Loi sur l'égalité, LEg; RS 151.1]), la garantie générale de l'égalité de traitement de l'art. 8 al. 1 Cst. ne confère pas directement un droit subjectif à un salaire égal en cas de rémunération discriminatoire non fondée sur le sexe, mais seulement un droit à la suppression de l'inégalité. Ainsi, à la différence de la garantie d'une rémunération égale de l'homme et de la femme, la garantie générale de l'égalité de traitement ne confère pas en droit fédéral une prétention directe au paiement d'un salaire égal à titre rétroactif. La Constitution exige seulement que l'inégalité soit éliminée d'une manière appropriée et dans un délai raisonnable (voir <ref-ruling> consid. 3.6 et 3.7 p. 109 ss).
La personne concernée peut en principe invoquer en tout temps la garantie générale de l'art. 8 al. 1 Cst. Le fait d'accepter des conditions d'engagement discriminatoires et de les tolérer, sans exiger un correctif, n'équivaut pas en soi à une renonciation à faire valoir un droit. On ne saurait, en effet, restreindre la possibilité de contester le salaire initialement fixé sous peine de laisser subsister des situations non conformes à la Constitution fédérale ou à des normes impératives de droit public (arrêt 8C_943/2011 du 26 novembre 2012 consid. 5.3).
6.2. La recourante fonde son droit à l'égalité de traitement sur un seul cas, à savoir celui de B._, issu de la même classe d'aspirants qu'elle. Comme l'ont toutefois constaté les premiers juges, ce cas est différent de celui de la recourante. Il concerne un policier qui, avant son engagement au service de l'Etat du Valais, avait été incorporé dans un autre corps (cantonal) de police. La recourante n'allègue pas que d'autres agents, au bénéfice d'une expérience professionnelle en dehors de la police, aient bénéficié à ce titre de parts d'expérience au moment de leur engagement. Même si les situations à comparer ne sont pas fondamentalement différentes, la recourante ne saurait, quoi qu'il en soit, revendiquer en application du droit à l'égalité un avantage dont elle ne prétend pas qu'il a été accordé aux autres agents en dehors de la situation exceptionnelle évoquée. Le grief soulevé ici doit être écarté.
7.
Indépendamment du droit à l'égalité, il convient encore d'examiner si la recourante peut, malgré le temps écoulé, invoquer l'art. 12 al. 4 OTMPC.
7.1. Selon la jurisprudence, le simple fait de tarder à faire valoir son droit en justice ne constitue pas un abus de droit (<ref-ruling> consid. 6.4 p. 239; <ref-ruling> consid. 3.3 p. 176; <ref-ruling> consid. 3g p. 19). Avant l'écoulement du délai de prescription, une péremption du droit d'action du créancier qui a tardé à exercer sa prétention ne peut être admise qu'avec réserve et en cas de circonstances tout à fait particulières, sous peine de vider de son sens l'institution de la prescription (ATF <ref-ruling> consid. 3g p. 19; <ref-ruling> consid. 2 p. 274; arrêt 4C.55/2007 du 26 avril 2007 consid. 6.2.3). Il faut ainsi qu'à l'écoulement du temps s'ajoutent des circonstances qui font apparaître l'exercice du droit comme étant en contradiction irrémédiable avec l'inaction antérieure du créancier et donc comme contraire aux règles de la bonne foi (ATF <ref-ruling> consid. 3g p. 19; <ref-ruling> consid. 2 p. 431; <ref-ruling> consid. 3b p. 232). De telles circonstances doivent être admises lorsque le silence du créancier permettait de conclure avec certitude à une renonciation à faire valoir son droit ou lorsque son inaction a engendré des inconvénients pour l'autre partie (arrêt 4C.55/2007, précité).
7.2. Dans le cas particulier, la recourante a fait valoir sa prétention à une augmentation de salaire en 2003. L'avis du service juridique lui a été communiqué en septembre de la même année. Par la suite, la recourante a entrepris, sans succès, diverses démarches. Le 23 mai 2007, le juriste de l'état-major de la police a déclaré vouloir mettre un terme à la procédure en confirmant en tous points les conclusions de l'avis de droit du service juridique. Par la suite, en juin 2010, le syndicat de la police valaisanne est intervenu en faveur de l'intéressée auprès de son supérieur hiérarchique. Le 28 juillet 2010, la recourante a écrit au président du Conseil d'Etat pour l'informer de sa situation et lui demander d'accéder enfin à sa demande. Le même jour, elle a envoyé une copie de son dossier à la conseillère d'Etat en charge du Département de la sécurité, des affaires sociales et de l'intégration. Enfin, n'ayant apparemment pas reçu de réponse, elle a saisi le Conseil d'Etat par son écriture du 28 décembre 2012 en lui demandant de statuer sur son cas et de rendre au besoin une décision susceptible de recours.
La question de savoir dans quelle mesure la recourante était déjà renseignée au moment de son engagement sur le salaire fixé et ses composantes peut demeurer indécise. En effet, sur le vu de la jurisprudence susmentionnée, l'acceptation par la recourante de son traitement initial ne saurait, quoi qu'il en soit, s'interpréter comme une renonciation par actes concluants à des prétentions de salaire plus élevées. Il en va de même de son silence jusqu'en 2003, date à laquelle elle a entrepris une première démarche, probablement après avoir appris que B._ avait bénéficié d'une augmentation de traitement. Les éléments relevés ci-dessus laissent apparaître que la recourante a depuis lors régulièrement manifesté son désaccord avec ses conditions salariales. Aucune circonstance particulière ne permet donc de retenir l'existence d'un abus de droit, respectivement d'un comportement contraire aux règles de la bonne foi, au motif que l'intéressée aurait tardé à faire valoir ses prétentions. Par conséquent, c'est à tort que le Conseil d'Etat et les premiers juges ont refusé pour ce motif d'entrer en matière sur sa demande. On ne voit pas, d'autre part, quel inconvénient pour l'employeur - sinon d'ordre purement administratif - justifierait une péremption de celle-ci.
7.3. Il convient dès lors d'annuler le jugement attaqué et de renvoyer la cause à la Cour cantonale pour qu'elle examine le bien-fondé des prétentions invoquées, étant précisé que le présent arrêt ne préjuge pas de l'appréciation qui pourrait être faite sur le fond et, le cas échéant, sur les effets dans le temps d'une éventuelle augmentation, ainsi que sur la question de la prescription.
8.
Les frais judiciaires doivent être mis à la charge du canton du Valais, qui succombe et qui défend un intérêt patrimonial (art. 66 al. 1 et 4 in fine LTF; cf. <ref-ruling> consid. 8.1.4 p. 40). Le canton versera une indemnité de dépens à la recourante qui obtient gain de cause (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est partiellement admis. La décision attaquée est annulée et la cause est renvoyée à la juridiction cantonale pour nouveau jugement au sens des motifs.
2.
Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge du canton du Valais.
3.
Le canton du Valais versera à la recourante une indemnité de 2'800 fr. au titre de dépens pour la procédure fédérale.
4.
Le présent arrêt est communiqué aux parties et à la Cour de droit public du Tribunal cantonal du canton du Valais.
Lucerne, le 30 juillet 2014
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
La Présidente : La Greffière :
Leuzinger von Zwehl